oj.uz

Submission #887538

# Submission time Handle Problem Language Result Execution time Memory
887538 2023-12-14T17:35:47 Z Ahmed57 Copy and Paste 3 (JOI22_copypaste3) C++17
0 / 100
 13 ms 63972 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63972 KB Output is correct
2 Correct 8 ms 63836 KB Output is correct
3 Incorrect 8 ms 63836 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 63876 KB Output is correct
2 Incorrect 8 ms 63836 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63972 KB Output is correct
2 Correct 8 ms 63836 KB Output is correct
3 Incorrect 8 ms 63836 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63972 KB Output is correct
2 Correct 8 ms 63836 KB Output is correct
3 Incorrect 8 ms 63836 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63972 KB Output is correct
2 Correct 8 ms 63836 KB Output is correct
3 Incorrect 8 ms 63836 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 63972 KB Output is correct
2 Correct 8 ms 63836 KB Output is correct
3 Incorrect 8 ms 63836 KB Output isn't correct
4 Halted 0 ms 0 KB -