QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #103611 | #6300. Best Carry Player 2 | MIT01# | TL | 4ms | 3608kb | C++17 | 2.2kb | 2023-05-07 04:16:12 | 2023-05-07 04:16:15 |
Judging History
answer
// #pragma GCC optimize("-Ofast","-ffast-math","-funroll-all-loops")
#include <bits/stdc++.h>
using namespace std;
#define ll __int128
#define db double
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define mod 998244353
#define vi vector<int>
const int maxn = 2000005;
const int S = 37;
template<typename T> bool chkmin(T &a, T b) {
return (b < a) ? (a = b, 1) : 0;
}
template<typename T> bool chkmax(T &a, T b) {
return (b > a) ? (a = b, 1) : 0;
}
ll dp[S + 2][3][S]; // next undet: i; j many <
int dig[S];
int main() {
int t;
cin >> t;
while (t--) {
ll x;
int k;
long long inp;
cin >> inp >> k;
x = inp;
for (int j = 0; j < S; j++) {
dig[j] = x % 10;
x /= 10;
}
ll inf = 3e18;
inf = inf * inf;
for (int i = 0; i < S + 2; i++)
for (int j = 0; j < 3; j++)
for (int k = 0; k < S; k++)
dp[i][j][k] = inf;
dp[0][1][0] = 0;
ll pw = 1;
for (int i = 0; i < S; i++) {
for (int u = 0; u < 3; u++)
for (int v = 0; v < S; v++) {
if (dp[i][u][v] > inf) continue;
for (int w = 0; w < 10; w++) {
// if (i == S - 1 && w >= 4) continue;
ll cc = dp[i][u][v] + w * pw;
int eu = 0, ev = v;
if (w > dig[i]) eu = 2;
else if (w == dig[i]) eu = u;
else eu = 0;
if (!eu) ev += 1;
chkmin(dp[i + 1][eu][ev], cc);
}
}
pw = pw * 10;
}
ll ans = dp[S][2][k] - inp;
vi otp;
while (ans) {
otp.pb(ans % 10);
ans /= 10;
}
reverse(otp.begin(), otp.end());
for (auto v : otp) printf("%d", v);
printf("\n");
// cout << ans << '\n';
// cout << dp[S][2][k] - stx << '\n';
}
return 0;
}
/*
4
12345678 0
12345678 5
12345678 18
990099 5
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3600kb
input:
4 12345678 0 12345678 5 12345678 18 990099 5
output:
1 54322 999999999987654322 9910
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 4ms
memory: 3608kb
input:
21 999990000099999 0 999990000099999 1 999990000099999 2 999990000099999 3 999990000099999 4 999990000099999 5 999990000099999 6 999990000099999 7 999990000099999 8 999990000099999 9 999990000099999 10 999990000099999 11 999990000099999 12 999990000099999 13 999990000099999 14 999990000099999 15 999...
output:
100000 10000 1000 100 10 1 900001 9900001 99900001 999900001 10000000001 9999910000 9999901000 9999900100 9999900010 9999900001 9000009999900001 99000009999900001 999000009999900001 99999999999999999900000000000000000 1000000000000000000
result:
ok 21 lines
Test #3:
score: -100
Time Limit Exceeded
input:
100000 119111011091190000 10 1911011191011999 16 110099199000119 0 19009911191091011 13 199090909919000900 17 19009010011919110 5 90910190019900091 18 10911100000101111 1 110090011101119990 4 100909999119090000 12 90901119109011100 2 111010119991090101 4 900991019109199009 5 100919919990991119 8 911...
output:
88988908810000 8088988808988001 10 88808908989 9800909090080999100 80890 909089809980099909 9 80010 9090000880910000 8900 9909 991 9008900 8880880090 8080090801 8009900808909899 80880898981 909 8800909 99988889901 89908888089 980908890980099000 100 9889801 81 908890008099900891 880990801 9998099 890...