Submission #622921

#	Time	Username	Problem	Language	Result	Execution time	Memory
622921		CSQ31	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	557 ms	73844 KiB

copypaste3

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll INF = 1e18;
ll dp[2500][2500];
int nxt[2500][2500];
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	string s;
	ll a,b,c;
	cin>>n>>s>>a>>b>>c;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			dp[i][j] = INF;
			nxt[i][j] = n;
		}
	}
	for(int i=0;i<n;i++){
		vector<int>z(n,0);
		vector<bool>hav(n,0);
		string t = s.substr(i,n-i);
		int cur = 1;
		int l = 0,r = 0;
		//cout<<"at"<<" "<<i<<'\n';
		for(int j=1;j<n-i;j++){
			if(j<=r)z[j] = min(r-j+1,z[j-l]);
			while(j+z[j]<n-i && t[j+z[j]] == t[z[j]])z[j]++;
			if(j+z[j]-1>r){
				l = j;
				r = j+z[j]-1;
			}
			while(cur<=j && cur<=z[j]){
				//cout<<i<<" "<<i+cur-1<<" "<<i+j<<'\n';
				nxt[i][i+cur-1] = i+j;
				cur++;
			}
		}
		/*
		for(int j=0;j<n;j++)cout<<z[j]<<" ";
		cout<<'\n';
		for(int j=i;j<n;j++)cout<<nxt[i][j]<<" ";
		cout<<'\n';
		* */
		
	}
	for(int i=0;i<n;i++)dp[i][i] = a+b;
	for(int len=0;len<n;len++){
		for(int i=0;i+len<n;i++){
			int r = i+len;
			if(dp[i][r] == INF)continue;
			//cout<<i<<" "<<r<<" "<<dp[i][r]<<'\n';
			if(r+1<n)dp[i][r+1] = min(dp[i][r] + a,dp[i][r+1]);
			if(i)dp[i-1][r] = min(dp[i][r]+a,dp[i-1][r]);
			ll cur = c;
			int pos = i;
			while(pos<n){
				int jump = nxt[pos][pos+len];
				if(jump>=n)break;
				cur+=(jump-(pos+len)-1)*1LL*a;
				cur+=c;
				dp[i][jump+len] = min(dp[i][jump+len],dp[i][r] + cur+b);
				pos = jump;
			}
		}
	}
	cout<<dp[0][n-1] - b<<'\n';
	
	
}

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