Submission #551903

#	Time	Username	Problem	Language	Result	Execution time	Memory
551903		Antekb	Copy and Paste 3 (JOI22_copypaste3)	C++14	100 / 100	678 ms	34008 KiB

copypaste3

#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
using ll = long long;
const int N=2505;
ll dp[N][N];
int main(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	int A, B, C;
	cin>>A>>B>>C;
	for(int l=1; l<=n; l++){
		for(int i=0; i<=n-l; i++){
			dp[i][i+l-1]=max({dp[i][i+l-1], dp[i][i+l-2], dp[i+1][i+l-1]});
		}
		ll pot=1;
		int bas=124338541;
		ll hasz=0;
		for(int i=0; i<l; i++){
			pot*=bas;	
		}
		vector<pair<ll, int> > V;
		for(int i=0; i<n; i++){
			hasz*=bas;
			hasz+=s[i];
			if(i>=l)hasz-=pot*ll(s[i-l]);
			if(i>=l-1)V.push_back({hasz, i});
		}
		vector<int> par(n, -1);
		sort(V.begin(), V.end());
		for(int i=0; i<=n-l; i++){
			//cout<<V[i].st<<","<<V[i].nd<<" ";
			int t=upper_bound(V.begin(), V.end(), make_pair(V[i].st, V[i].nd-l))-V.begin();
			t--;
			if(t>=0 && V[t].st==V[i].st)par[V[i].nd]=V[t].nd;
		}
		//cout<<"\n";
		for(int i=0; i<n; i++){
			//cout<<i<<" "<<par[i]<<"\n";
			int j=2, p=par[i];
			while(p!=-1){
				//if(l==3 && i==7 && p==4)cout<<"a"<<" "<<(j-1)*l*1ll*A<<" "<<dp[p-l+1][p]<<" "<<B+j*1ll*C<<"\n";
				dp[p-l+1][i]=max(dp[p-l+1][i], (j-1)*l*1ll*A+dp[p-l+1][p]-B-j*1ll*C);
				p=par[p];
				j++;
			}
		}
	}
	for(int i=0; i<n; i++){
		for(int j=i; j<n; j++){
			//cout<<A*(j-i+1)-dp[i][j]<<" \n"[j==n-1];
		}
	}
	cout<<A*1ll*n-dp[0][n-1];
}

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