QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #39792 | #2835. Number Theory | MoQz | TL | 0ms | 6012kb | C++ | 1.5kb | 2022-07-13 15:57:10 | 2022-07-13 15:57:13 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
int t;
char s[5011];
int n,f[2][511][5011];
int mid=2500,mid2=25;
int Abs(int x){
if(x<0)return -x;
return x;
}
int Min(int x,int y){
return x<y?x:y;
}
int Max(int x,int y){
return x>y?x:y;
}
int main(){
// freopen("ones.in","r",stdin);
// freopen("ones.out","w",stdout);
// scanf("%d",&t);
t=1;
while(t){
// --t;
char c=getchar();
while(c<'0'||c>'9'){
c=getchar();
if(c==EOF)break;
}
if(c==EOF)break;
n=0;
while(c>='0'&&c<='9'){
s[n++]=c;
c=getchar();
}
int smax=0;
fo(i,0,n-1){
smax=Max(smax,s[i]-'0');
}
if(smax<=1)mid=50;
else mid=250;
fo(j,-mid2,mid2){
fo(k,-mid,mid)
f[1][j+mid2][k+mid]=99999999;
}
fo(i,-mid2,mid2){
f[1][i+mid2][i+mid]=Abs(i)*(n+1);
}
fo(i,0,n-1){
int u=(i&1),v=(u^1);
fo(j,-mid2,mid2){
fo(k,-mid,mid)
f[u][j+mid2][k+mid]=99999999;
}
fo(j,-mid2,mid2){
fo(k2,-mid,mid){
if(f[v][j+mid2][k2+mid]!=99999999){
int r=k2+j*10-s[i]+'0';
fo(k3,-mid2-r,mid2-r){
int k=k3+r;
if(Abs(k2+k3)<=mid){
f[u][k+mid2][k2+k3+mid]=Min(f[u][k+mid2][k2+k3+mid],f[v][j+mid2][k2+mid]+Abs(k3)*(n-i));
}
}
}
}
}
}
int ans=99999999;
fo(i,-mid,mid){
ans=Min(ans,f[(n-1)&1][mid2][i+mid]);
}
printf("%d\n",ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 6012kb
input:
12 100 998244353
output:
3 5 76
result:
ok 3 lines
Test #2:
score: -100
Time Limit Exceeded
input:
4296 5370 8014 9532 6311 4070 2541 4782 5630 1487 2916 454 2020 5650 1851 5885 3556 6533 5044 1780 5746 5605 7860 4416 4495 8081 2416 3534 6045 3348 4536 8725 3505 1074 1531 937 7954 4451 7052 9586 3468 2679 6085 9908 3630 8046 6282 2883 9021 1436 5201 8166 8986 2167 7780 4156 101 3753 5732 5173 118...
output:
29 36 28 27 35 36 22 30 32 22 33 15 20 30 28 32 19 29 40 22 34 34 30 26 30 35 24 23 42 18 26 28 31 14 22 22 33 22 43 30 21 24 42 19 30 33 43 30 21 18 34 36 21 18 19 34 6 30 35 42 14 27 36 32 23 25 30 35 28 22 32 27 41 39 26 37 30 28 39 35 22 24 32 44 35 36 35 42 22 22 31 35 25 32 32 15 17 33 38 31 2...