oj.uz

Submission #890232

# Submission time Handle Problem Language Result Execution time Memory
890232 2023-12-20T17:59:24 Z amirhoseinfar1385 Copy and Paste 3 (JOI22_copypaste3) C++17
5 / 100
 260 ms 146772 KB 
#include<bits/stdc++.h>
using namespace std;
const long long maxn=2500+10;
long long lcp[maxn][maxn],nxt[maxn][maxn],n;
long long dp[maxn][maxn],a,b,c,inf=1e15;
string s;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>s;
	cin>>a>>b>>c;
	for(long long i=n-1;i>=0;i--){
		for(long long j=i+1;j<n;j++){
			if(s[i]==s[j]){
				lcp[i][j]=lcp[i+1][j+1]+1;
			}
		}
	}
	for(long long i=0;i<maxn;i++){
		for(long long j=0;j<maxn;j++){
			nxt[i][j]=n+3;
		}
	}
	for(long long i=0;i<n;i++){
		for(long long j=n-1;j>i;j--){
			nxt[i][min(lcp[i][j],j-i)]=j;
		}
		for(long long j=n;j>=0;j--){
			nxt[i][j]=min(nxt[i][j],nxt[i][j+1]);
		}
	}
	for(long long i=0;i<maxn;i++){
		for(long long j=0;j<maxn;j++){
			dp[i][j]=inf;
		}
	}
	for(long long i=n-1;i>=0;i--){
		dp[i][i]=a;
		for(long long j=i+1;j<n;j++){
			dp[i][j]=min(dp[i][j],min(dp[i+1][j],dp[i][j-1])+a);
		}
		for(long long j=1;j<n;j++){
			long long ted=2;
			long long z=dp[i][j+i-1];
			for(long long h=nxt[i][j];h!=n+3;h=nxt[h][j]){
			//	cout<<i<<" "<<h<<" "<<j<<" "<<ted<<" "<<z<<" "<<endl;
				dp[i][h+j-1]=min(dp[i][h+j-1],z+ted*c+b+a*(h+j-i-(ted*j)));
				ted++;
			}
		}
	}
	cout<<dp[0][n-1]<<"\n";
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 99160 KB Output is correct
2 Correct 18 ms 98932 KB Output is correct
3 Incorrect 20 ms 98908 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 99160 KB Output is correct
2 Correct 16 ms 98908 KB Output is correct
3 Correct 132 ms 133968 KB Output is correct
4 Correct 149 ms 136472 KB Output is correct
5 Correct 181 ms 140352 KB Output is correct
6 Correct 215 ms 144312 KB Output is correct
7 Correct 255 ms 146516 KB Output is correct
8 Correct 260 ms 146772 KB Output is correct
9 Correct 253 ms 146736 KB Output is correct
10 Correct 17 ms 98908 KB Output is correct
11 Correct 17 ms 99060 KB Output is correct
12 Correct 16 ms 98908 KB Output is correct
13 Correct 19 ms 98896 KB Output is correct
14 Correct 17 ms 98904 KB Output is correct
15 Correct 16 ms 98900 KB Output is correct
16 Correct 16 ms 99164 KB Output is correct
17 Correct 18 ms 98944 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 99160 KB Output is correct
2 Correct 18 ms 98932 KB Output is correct
3 Incorrect 20 ms 98908 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 99160 KB Output is correct
2 Correct 18 ms 98932 KB Output is correct
3 Incorrect 20 ms 98908 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 99160 KB Output is correct
2 Correct 18 ms 98932 KB Output is correct
3 Incorrect 20 ms 98908 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 99160 KB Output is correct
2 Correct 18 ms 98932 KB Output is correct
3 Incorrect 20 ms 98908 KB Output isn't correct
4 Halted 0 ms 0 KB -