Submission #1206231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206231		emptypringlescan	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	536 ms	107812 KiB

copypaste3

#include <bits/stdc++.h>
using namespace std;
const long long mod=88888888888889;
long long dp[2505][2505],hsh[2505][2505];
int prv[2505][2505];
int n;
long long a,b,c;
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    string s;
    cin >> s;
    cin >> a >> b >> c;
    for(int i=0; i<n; i++){
		long long cur=0;
		for(int j=i; j<n; j++){
			cur=(cur*26ll+s[j]-'a')%mod;
			hsh[i][j]=cur;
		}
	}
	memset(prv,-1,sizeof(prv));
	unordered_map<long long,pair<int,vector<int> > > oop;
	for(int i=1; i<=n; i++){
		oop.clear();
		for(int j=i-1; j<n; j++){
			long long me=hsh[j-i+1][j];
			int pt=oop[me].first;
			while(pt<(int)oop[me].second.size()&&oop[me].second[pt]<j-i+1){
				pt++;
			}
			if(pt!=0) prv[j-i+1][j]=oop[me].second[pt-1];
			oop[me].first=pt;
			oop[me].second.push_back(j);
		}
	}
	for(int i=0; i<n; i++) for(int j=0; j<n; j++) dp[i][j]=1e16;
	for(int i=0; i<n; i++){
		for(int j=i; j>=0; j--){
			dp[j][i]=min(dp[j][i],(long long)(i-j+1)*a);
			if(j<i) dp[j][i]=min({dp[j][i],dp[j][i-1]+a,dp[j+1][i]+a});
			int cur=prv[j][i],num=2;
			while(cur!=-1){
				dp[cur-(i-j)][i]=min(dp[cur-(i-j)][i],dp[j][i]+b+(long long)num*c+(long long)(i-cur-(num-1)*(i-j+1))*a);
				cur=prv[cur-(i-j)][cur];
				num++;
			}
		}
	}/*
	for(int i=0; i<n; i++) {
		for(int j=i; j<n; j++) cout << dp[i][j] << ' ';
		cout << '\n';
	}*/
	cout << 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