QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #769912 | #6300. Best Carry Player 2 | 2020zym | WA | 1ms | 3880kb | C++14 | 1.1kb | 2024-11-21 19:52:42 | 2024-11-21 19:52:42 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
long long inf=2e18;
long long f[21][10][21][2];
int zan[21];
int main(){
int T;
scanf("%d",&T);
while(T--){
long long n;
int tot=0,K;
scanf("%lld%d",&n,&K);
for(int i=1;i<=20;i++)zan[i]=0;
while(n)zan[++tot]=n%10,n/=10;
for(int i=0;i<=20;i++)
for(int j=0;j<=9;j++)
for(int k=0;k<=20;k++)
f[i][j][k][0]=f[i][j][k][1]=inf;
f[0][0][0][0]=0;
long long ww=1,minn=inf;
for(int i=1;i<=18;i++,ww*=10){
for(int j=0;j<=9;j++){
for(int k=0;k<=K;k++){
for(int k2=0;k2<=1;k2++)
if(f[i-1][j][k][k2]<inf){
for(int k3=0;k3<=9;k3++){
int op=k3+j+zan[i];
int jj=(op/10),kk=(op>=10);
if(k+kk<=K){
f[i][jj][kk+k][k2|(k3>0)]=min(f[i][jj][kk+k][k2|(k3>0)],f[i-1][j][k][k2]+k3*ww);
}
}
}
}
}
}
for(int i=1;i<=18;i++){
if(f[i][0][K][1]<inf)
minn=min(minn,f[i][0][K][1]);
if(zan[i+1]==0){
for(int j=0;j<=9;j++)
minn=min(minn,f[i][j][K][1]);
}
}
if(minn>=inf)printf("-1\n");
else printf("%lld\n",minn);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3880kb
input:
4 12345678 0 12345678 5 12345678 18 990099 5
output:
1 54322 999999999987654322 9910
result:
ok 4 lines
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3828kb
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 -1 -1
result:
wrong answer 20th lines differ - expected: '99999999999999999900000000000000000', found: '-1'