Submission #556670

#	Time	Username	Problem	Language	Result	Execution time	Memory
556670		mosiashvililuka	Copy and Paste 3 (JOI22_copypaste3)	C++14	100 / 100	577 ms	132060 KiB

copypaste3

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,A,B,C,dp[2504][2504],f[2504][2504],g[2504][2504];
string s;
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>s;s="0"+s;
	cin>>A>>B>>C;
	for(i=a; i>=1; i--){
		for(j=a; j>i; j--){
			if(s[i]!=s[j]){
				f[i][j]=0;continue;
			}
			f[i][j]=f[i+1][j+1]+1;
		}
	}
	for(i=0; i<=a+1; i++){
		for(j=0; j<=a+1; j++){
			g[i][j]=a+2;
			if(i<=j) dp[i][j]=A*a; else dp[i][j]=0;
		}
	}
	for(i=1; i<=a; i++){
		jj=i+1;
		for(j=i; j<=a; j++){
			if(jj>a) break;
			if(jj<=j||f[i][jj]<j-i+1){
				jj++;j--;
				continue;
			}
			g[i][j-i+1]=jj;
		}
	}
	for(i=a; i>=1; i--){
		for(j=i; j<=a; j++){
			dp[i][j]=min(dp[i][j-1]+A,dp[i][j]);
			dp[i][j]=min(dp[i+1][j]+A,dp[i][j]);
			jj=j-i+1;
			c=i;d=1;
			while(1){
				c=g[c][jj];d++;
				if(c>a) break;
				//cout<<i<<" "<<j<<"   "<<c<<" "<<d<<"\n";
				e=(c+jj-1)-i+1-(d*jj);
				zx=B+C*d+e*A+dp[i][j];
				/*if(dp[i][c+jj-1]>zx){
					cout<<"update: dp["<<i<<"]["<<c+jj-1<<"]"<<"="<<zx<<"      "<<i<<" "<<j<<" "<<c<<" "<<d<<"\n";
				}*/
				dp[i][c+jj-1]=min(dp[i][c+jj-1],zx);
			}
		}
	}
	cout<<dp[1][a];
	return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 5 / 5
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 32 / 32
• Subtask 6: 38 / 38