Submission #861005

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
861005	2023-10-15T06:25:16 Z	willychan	Copy and Paste 3 (JOI22_copypaste3)	C++14	15 / 100	3000 ms	1112 KB

copypaste3

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include<bits/extc++.h>
//__gnu_pbds
#define pt pair<pair<int,int>,pair<int,int> >
#define xl first.first
#define xr first.second
#define yl second.first
#define yr second.second

const int N = 205;
ll dp[N][N];
string s;
int a,b,c;

const int MOD = 1e9+7;
int hsh[N];
int ppow[N];
int get(int l,int r){
	ll ans = hsh[r];
	ans = (ans-(1LL*hsh[l-1]*ppow[r-l+1])%MOD)%MOD;
	if(ans<0) ans+=MOD;
	return ans;
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n;cin>>n;
	cin>>s;
	cin>>a>>b>>c;	
	ppow[0]=1;
	for(int i=1;i<=n;i++){
		hsh[i] = (1LL*hsh[i-1]*31)%MOD;
		hsh[i]+=(s[i-1]-'a');
		hsh[i]%=MOD;
		ppow[i] = (31LL*ppow[i-1])%MOD;
	}
	for(int i=0;i<=n+1;i++){
		for(int j=i;j<=n+1;j++) dp[i][j]=1LL*(j-i+1)*a+b;
	}
	for(int l=0;l<n;l++){
		for(int i=1;i+l<=n;i++){
			for(int l2=0;l2<l;l2++){
				for(int j=1;j+l2<=n;j++){
					ll re = 0;
					for(int h=i;h<=i+l;h++){
						if(h+l2<=i+l && get(h,h+l2)==get(j,j+l2)){
							h= h+l2;
							re+=c;
						}else{
							re+=a;	
						}
					}
				//	if(dp[i][i+l]>re+dp[j][j+l2]+c){
				//		cout<<i<<" "<<i+l<<"<-"<<j<<" "<<j+l2<<"\n";
				//	}
					dp[i][i+l] = min(dp[i][i+l],re+dp[j][j+l2]+b);
				}
			}
		//	cout<<dp[i][i+l]<<" ";
		}
		//cout<<"\n";
	}
	cout<<dp[1][n]-b<<"\n";
	return 0;
}

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	436 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct

Subtask #2

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Runtime error	2 ms	1112 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-

Subtask #3

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	436 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	1 ms	468 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	344 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	3 ms	348 KB	Output is correct
22	Correct	8 ms	348 KB	Output is correct
23	Correct	8 ms	348 KB	Output is correct
24	Correct	7 ms	348 KB	Output is correct
25	Correct	7 ms	348 KB	Output is correct
26	Correct	7 ms	596 KB	Output is correct
27	Correct	5 ms	348 KB	Output is correct
28	Correct	4 ms	524 KB	Output is correct
29	Correct	8 ms	500 KB	Output is correct
30	Correct	7 ms	348 KB	Output is correct
31	Correct	7 ms	516 KB	Output is correct
32	Correct	7 ms	520 KB	Output is correct
33	Correct	7 ms	348 KB	Output is correct
34	Correct	0 ms	348 KB	Output is correct
35	Correct	0 ms	348 KB	Output is correct
36	Correct	0 ms	468 KB	Output is correct
37	Correct	1 ms	348 KB	Output is correct
38	Correct	0 ms	348 KB	Output is correct
39	Correct	3 ms	348 KB	Output is correct

Subtask #4

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	436 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	1 ms	468 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	344 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	3 ms	348 KB	Output is correct
22	Correct	8 ms	348 KB	Output is correct
23	Correct	8 ms	348 KB	Output is correct
24	Correct	7 ms	348 KB	Output is correct
25	Correct	7 ms	348 KB	Output is correct
26	Correct	7 ms	596 KB	Output is correct
27	Correct	5 ms	348 KB	Output is correct
28	Correct	4 ms	524 KB	Output is correct
29	Correct	8 ms	500 KB	Output is correct
30	Correct	7 ms	348 KB	Output is correct
31	Correct	7 ms	516 KB	Output is correct
32	Correct	7 ms	520 KB	Output is correct
33	Correct	7 ms	348 KB	Output is correct
34	Correct	0 ms	348 KB	Output is correct
35	Correct	0 ms	348 KB	Output is correct
36	Correct	0 ms	468 KB	Output is correct
37	Correct	1 ms	348 KB	Output is correct
38	Correct	0 ms	348 KB	Output is correct
39	Correct	3 ms	348 KB	Output is correct
40	Correct	1092 ms	604 KB	Output is correct
41	Execution timed out	3055 ms	604 KB	Time limit exceeded
42	Halted	0 ms	0 KB	-

Subtask #5

0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	436 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	1 ms	468 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	344 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	3 ms	348 KB	Output is correct
22	Correct	8 ms	348 KB	Output is correct
23	Correct	8 ms	348 KB	Output is correct
24	Correct	7 ms	348 KB	Output is correct
25	Correct	7 ms	348 KB	Output is correct
26	Correct	7 ms	596 KB	Output is correct
27	Correct	5 ms	348 KB	Output is correct
28	Correct	4 ms	524 KB	Output is correct
29	Correct	8 ms	500 KB	Output is correct
30	Correct	7 ms	348 KB	Output is correct
31	Correct	7 ms	516 KB	Output is correct
32	Correct	7 ms	520 KB	Output is correct
33	Correct	7 ms	348 KB	Output is correct
34	Correct	0 ms	348 KB	Output is correct
35	Correct	0 ms	348 KB	Output is correct
36	Correct	0 ms	468 KB	Output is correct
37	Correct	1 ms	348 KB	Output is correct
38	Correct	0 ms	348 KB	Output is correct
39	Correct	3 ms	348 KB	Output is correct
40	Correct	1092 ms	604 KB	Output is correct
41	Execution timed out	3055 ms	604 KB	Time limit exceeded
42	Halted	0 ms	0 KB	-

Subtask #6

0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	436 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Runtime error	2 ms	1112 KB	Execution killed with signal 11
14	Halted	0 ms	0 KB	-