Submission #551762

#	Time	Username	Problem	Language	Result	Execution time	Memory
551762		kshitij_sodani	Copy and Paste 3 (JOI22_copypaste3)	C++14	100 / 100	1092 ms	147620 KiB

copypaste3

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
const llo mod=1e9+7;
bool par[2501][2501][13];
llo ne[2501][2501];//
vector<llo> pre[2501];
llo it[2501];
llo dp[2501][2501];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo n;
	cin>>n;
	string s;
	cin>>s;
	for(llo i=0;i<n;i++){
		it[i]=s[i]-'0';
	}
	llo aa,bb,cc;
	cin>>aa>>bb>>cc;
	for(llo i=0;i<n;i++){
		for(llo j=i;j<n;j++){
			if(it[i]==it[j]){
				par[i][j][0]=1;
			}
			else{
				par[i][j][1]=1;
			}
		}
	}
	for(llo j=1;j<13;j++){
		for(llo i=0;i<n;i++){
			for(llo k=i;k<n;k++){
				if(k+(1<<j)-1>=n){
					par[i][k][j]=0;
					continue;
				}
				par[i][k][j]=min(par[i][k][j-1],par[i+(1<<(j-1))][k+(1<<(j-1))][j-1]);
			}
		}
	}
	for(llo i=0;i<n;i++){
		for(llo j=0;j<=n;j++){
			pre[j].clear();
		}
		for(llo j=i+1;j<n;j++){
			llo su=0;
			llo aa=i;
			llo bb=j;
			for(llo k=12;k>=0;k--){
				if(bb+(1<<k)-1<n){
					if(par[aa][bb][k]==1){
						aa+=(1<<k);
						bb+=(1<<k);
						su+=(1<<k);
					}
				}
			}
			if(su==0){
				continue;
			}
			su=min(su,j-i);
			pre[su].pb(j);
		}
		llo mi=n;
		for(llo j=n;j>=1;j--){
			for(auto jj:pre[j]){
				mi=min(mi,jj);
			}
			if(mi<n){
				ne[i][j]=mi;
				//cout<<i<<":"<<j<<":"<<ne[i][j]<<endl;
			}
			else{
				ne[i][j]=-1;
			}
			
		}
	}
	//return 0;
	for(llo i=0;i<n;i++){
		for(llo j=0;j<n;j++){
			dp[i][j]=1e18;
		}
	}
	for(llo ii=0;ii<n;ii++){
		for(llo i=0;i+ii<n;i++){
			llo j=i+ii;
			if(i==j){
				dp[i][j]=min(dp[i][j],aa);
			}
			else{
				dp[i][j]=min(dp[i][j],min(dp[i][j-1]+aa,dp[i+1][j]+aa));
			}
			llo cur=i;
			llo su2=0;
			llo zz=1;
			while(true){
				if(zz>1){
					dp[i][cur+ii]=min(dp[i][cur+ii],su2*aa+dp[i][j]+bb+cc*zz);
					/*if(i==2 and j==4){
						cout<<cur<<":"<<endl;
						cout<<su2<<":"<<dp[i][j]<<":"<<zz<<endl;
					}*/
				}
				//cout<<i<<",,"<<j<<":"<<cur<<endl;
				
			/*	if(ne[cur][j-i+1]==0){
					cout<<cur<<":"<<j-i+1<<endl;
					return 0;
				}*/
				if(ne[cur][j-i+1]==-1){
					break;
				}
				su2+=ne[cur][j-i+1]-(cur+ii)-1;
				zz++;
				cur=ne[cur][j-i+1];

			}
		}
	}
	//cout<<dp[2][7]<<endl;

	cout<<dp[0][n-1]<<endl;
	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