Submission #622907

#	Time	Username	Problem	Language	Result	Execution time	Memory
622907		CSQ31	Copy and Paste 3 (JOI22_copypaste3)	C++17	62 / 100	3071 ms	49228 KiB

copypaste3

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll INF = 1e18;
ll dp[2500][2500];
int main()
{
	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;
		}
	}
	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;
			for(int j=i+1+len;j+len<n;j++){
				//cout<<cur<<'\n';
				bool ok = 1;
				for(int k=0;k<=len;k++){
					if(s[j+k] != s[i+k]){
						ok = 0;
						break;
					}
				}
				if(!ok)cur+=a;
				else{
					//cout<<i<<" "<<r<<" "<<j<<" "<<j+len<<" "<<cur+b<<'\n';
					cur+=c;
					dp[i][j+len] = min(dp[i][j+len],dp[i][r] + cur+b);
					j+=len;
				}
			}
		}
	}
	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: 0 / 38