Submission #887540

#	Time	Username	Problem	Language	Result	Execution time	Memory
887540		Ahmed57	Copy and Paste 3 (JOI22_copypaste3)	C++17	30 / 100	978 ms	133152 KiB

copypaste3

#include <bits/stdc++.h>
using namespace std;
#define int long long
long long n,a,b,c;string s;
int lcp[201][201];
long long dp[201][201][201];
long long solve(int i,int l,int r){
	if(l==0&&r==n){
		return 0;
	}
	if(i==n){
		return 1e18;
	}
	if(dp[i][l][r]!=-1)return dp[i][l][r];
	long long cost = 0 , j = 0;
	long long c1 = solve(i+1,l,r);
	for(j = i;j<n;){
        int lol = (r-l<=lcp[j][l]?r-l:0);
        if(lol==0){
        	cost+=a;
        	if(j+1-i>r-l)c1 = min(c1,solve(0,i,j+1)+cost+b);
        	j++;
        	continue;
        }
        for(long long e = j+1;e<min(n+1,lol+j);e++){
            if(e-i>r-l)c1 = min(c1,solve(0,i,e)+cost+(e-j)*a+b);
        }
        cost+=min((r-l)*a,c);
        if(min(n,lol+j)-i>r-l)c1 = min(c1,solve(0,i,min(n,lol+j))+cost+b);
        j+=r-l;
	}
	return dp[i][l][r] = c1;
}
long long dp2[2501][2501];
long long solve2(int i,int cu){
	if(i==n){
		return 0;
	}
	if(dp2[i][cu]!=-1)return dp2[i][cu];
	long long c1 = solve2(i+1,cu)+a;
	if(cu&&i+cu<=n)c1 = min(c1,solve2(i+cu,cu)+c);
	if(i>cu)c1 = min(c1,solve2(0,i)+b);
	return dp2[i][cu] = c1;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>s>>a>>b>>c;
	memset(dp,-1,sizeof dp);
	bool bb = 1;
	for(int i = 1;i<n;i++){
		if(s[i]!=s[i-1]){
			bb = 0;
		}
	}
	if(bb){
		memset(dp2,-1,sizeof dp2);
		cout<<solve2(0,0)<<endl;
		return 0;
	}
	for(int i = 0;i<n;i++){
		for(int j = 0;j<n;j++){
			for(int k = 0;k<min(n-i,n-j);k++){
				if(s[i+k]==s[j+k]){
					lcp[i][j]++;
				}else break;
			}
		}
	}
	cout<<solve(0,0,0)-b<<endl;
}

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