Submission #11763

#	Time	Username	Problem	Language	Result	Execution time	Memory
11763		gs12117	Sequence (BOI14_sequence)	C++98	100 / 100	220 ms	26176 KiB

sequence

#include<stdio.h>
#define mmax(x,y) (((x)>(y))?(x):(y))
#define mmin(x,y) (((x)<(y))?(x):(y))
int n;
int a[100100];
long long int dpa[3][1<<9];
long long int dpb[3][1<<9][3][1<<9];
int p[8][100100][2];
long long int cans(int dep,int len){
	if(len==1){
		return dpa[p[dep][0][0]][p[dep][0][1]];
	}
	else if(len==2){
		return dpb[p[dep][0][0]][p[dep][0][1]][p[dep][1][0]][p[dep][1][1]];
	}
	else{
		int i,j;
		long long int ans,t;
		ans=1e17;
		for(i=0;i<10;i++){
			for(j=0;j<(len/10)+2;j++){
				p[dep+1][j][0]=0;
				p[dep+1][j][1]=0;
			}
			for(j=0;j<len;j++){
				if((i+j)%10==0){
					if(p[dep+1][(i+j)/10][0]<mmin(p[dep][j][0],1)){
						p[dep+1][(i+j)/10][0]=mmin(p[dep][j][0],1);
					}
					p[dep+1][(i+j)/10][1]|=p[dep][j][1];
				}
				else{
					if(p[dep+1][(i+j)/10][0]<(p[dep][j][0]&2)){
						p[dep+1][(i+j)/10][0]=(p[dep][j][0]&2);
					}
					p[dep+1][(i+j)/10][1]|=(p[dep][j][1]&((1<<9)-1-(1<<((i+j)%10-1))));
				}
			}
			t=cans(dep+1,(i+len-1)/10+1);
			if(ans>t*10+i)ans=t*10+i;
		}
		return ans;
	}
}
int main(){
	int i,j,k,l,ii;
	long long int t;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	for(i=0;i<3;i++){
		for(j=0;j<(1<<9);j++){
			if(i==0&&j==0)continue;
			dpa[i][j]=1e17;
			for(k=0;k<10;k++){
				if(k==0){
					if(dpa[i][j]>dpa[mmin(i,1)][j]*10+k)dpa[i][j]=dpa[mmin(i,1)][j]*10+k;
				}
				else{
					if(dpa[i][j]>dpa[i&2][j&((1<<9)-1-(1<<(k-1)))]*10+k)dpa[i][j]=dpa[i&2][j&((1<<9)-1-(1<<(k-1)))]*10+k;
				}
			}
		}
	}
	for(i=0;i<3;i++){
		for(j=0;j<(1<<9);j++){
			for(k=0;k<3;k++){
				for(l=0;l<(1<<9);l++){
					dpb[i][j][k][l]=1e17;
					for(ii=0;ii<10;ii++){
						if(ii==0){
							t=dpa[mmax(mmin(i,1),k&2)][j|(l&((1<<9)-1-(1<<(ii))))]*10+ii;
							if(dpb[i][j][k][l]>t)dpb[i][j][k][l]=t;
						}
						else if(ii==9){
							t=dpb[i&2][(j&((1<<9)-1-(1<<(ii-1))))][mmin(k,1)][l]*10+ii;
							if(dpb[i][j][k][l]>t)dpb[i][j][k][l]=t;
						}
						else{
							t=dpa[mmax(i,k)&2][(j&((1<<9)-1-(1<<(ii-1))))|(l&((1<<9)-1-(1<<(ii))))]*10+ii;
							if(dpb[i][j][k][l]>t)dpb[i][j][k][l]=t;
						}
					}
				}
			}
		}
	}
	for(i=0;i<n;i++){
		if(a[i]==0){
			p[0][i][0]=2;
		}
		else{
			p[0][i][1]=(1<<(a[i]-1));
		}
	}
	printf("%lld",cans(0,n));
}

• Subtask 1: 9 / 9
• Subtask 2: 33 / 33
• Subtask 3: 25 / 25
• Subtask 4: 33 / 33