답안 #890233

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
890233	2023-12-20T18:02:27 Z	amirhoseinfar1385	Copy and Paste 3 (JOI22_copypaste3)	C++17	1 / 100	21 ms	99116 KB

copypaste3

#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=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++;
			}
		}
		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);
		}
	}
	cout<<dp[0][n-1]<<"\n";
}

Subtask #1

1.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	98908 KB	Output is correct
2	Correct	16 ms	98908 KB	Output is correct
3	Correct	16 ms	99064 KB	Output is correct
4	Correct	16 ms	98904 KB	Output is correct
5	Correct	17 ms	98908 KB	Output is correct
6	Correct	17 ms	99048 KB	Output is correct
7	Correct	16 ms	98908 KB	Output is correct
8	Correct	18 ms	98868 KB	Output is correct
9	Correct	16 ms	99032 KB	Output is correct
10	Correct	17 ms	99056 KB	Output is correct

Subtask #2

0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	16 ms	99116 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3

0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	98908 KB	Output is correct
2	Correct	16 ms	98908 KB	Output is correct
3	Correct	16 ms	99064 KB	Output is correct
4	Correct	16 ms	98904 KB	Output is correct
5	Correct	17 ms	98908 KB	Output is correct
6	Correct	17 ms	99048 KB	Output is correct
7	Correct	16 ms	98908 KB	Output is correct
8	Correct	18 ms	98868 KB	Output is correct
9	Correct	16 ms	99032 KB	Output is correct
10	Correct	17 ms	99056 KB	Output is correct
11	Incorrect	16 ms	98908 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #4

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	98908 KB	Output is correct
2	Correct	16 ms	98908 KB	Output is correct
3	Correct	16 ms	99064 KB	Output is correct
4	Correct	16 ms	98904 KB	Output is correct
5	Correct	17 ms	98908 KB	Output is correct
6	Correct	17 ms	99048 KB	Output is correct
7	Correct	16 ms	98908 KB	Output is correct
8	Correct	18 ms	98868 KB	Output is correct
9	Correct	16 ms	99032 KB	Output is correct
10	Correct	17 ms	99056 KB	Output is correct
11	Incorrect	16 ms	98908 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #5

0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	98908 KB	Output is correct
2	Correct	16 ms	98908 KB	Output is correct
3	Correct	16 ms	99064 KB	Output is correct
4	Correct	16 ms	98904 KB	Output is correct
5	Correct	17 ms	98908 KB	Output is correct
6	Correct	17 ms	99048 KB	Output is correct
7	Correct	16 ms	98908 KB	Output is correct
8	Correct	18 ms	98868 KB	Output is correct
9	Correct	16 ms	99032 KB	Output is correct
10	Correct	17 ms	99056 KB	Output is correct
11	Incorrect	16 ms	98908 KB	Output isn't correct
12	Halted	0 ms	0 KB	-

Subtask #6

0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	98908 KB	Output is correct
2	Correct	16 ms	98908 KB	Output is correct
3	Correct	16 ms	99064 KB	Output is correct
4	Correct	16 ms	98904 KB	Output is correct
5	Correct	17 ms	98908 KB	Output is correct
6	Correct	17 ms	99048 KB	Output is correct
7	Correct	16 ms	98908 KB	Output is correct
8	Correct	18 ms	98868 KB	Output is correct
9	Correct	16 ms	99032 KB	Output is correct
10	Correct	17 ms	99056 KB	Output is correct
11	Incorrect	16 ms	99116 KB	Output isn't correct
12	Halted	0 ms	0 KB	-