Submission #887538

#	Time	Username	Problem	Language	Result	Execution time	Memory
887538		Ahmed57	Copy and Paste 3 (JOI22_copypaste3)	C++17	0 / 100	13 ms	63972 KiB

copypaste3

#include <bits/stdc++.h>
using namespace std;
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 1e9;
	}
	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;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>s>>a>>b>>c;
	memset(dp,-1,sizeof dp);
	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: 0 / 1
• Subtask 2: 0 / 5
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 32
• Subtask 6: 0 / 38