QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#39790 | #2835. Number Theory | MoQz | WA | 3ms | 6076kb | C++ | 1.3kb | 2022-07-13 15:49:27 | 2022-07-13 15:49:28 |
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;
scanf("%s",s);
n=strlen(s);
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: 0
Wrong Answer
time: 3ms
memory: 6076kb
input:
12 100 998244353
output:
3
result:
wrong answer 2nd lines differ - expected: '5', found: ''