QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#39790#2835. Number TheoryMoQzWA 3ms6076kbC++1.3kb2022-07-13 15:49:272022-07-13 15:49:28

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-13 15:49:28]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:6076kb
  • [2022-07-13 15:49:27]
  • 提交

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: ''