Submission #587567

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
587567	2022-07-02T05:43:46 Z	LastRonin	Copy and Paste 3 (JOI22_copypaste3)	C++14	15 / 100	2 ms	456 KB

copypaste3

#pragma GCC optimize("O3")

#include <bits/stdc++.h> 
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define pill pair<ll, ll>
#define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

const int N = 30 + 1;
const ll hsh[2] = {1555555699, 1222222763};
const ll P = 113;

ll n;
string a;
ll dp[N][N], dp2[N];
ll A, B, C;

bool eq[N][N][N];

int main() {
	speed;
	cin >> n;
	cin >> a;
	cin >> A >> B >> C;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			dp[i][j] = 1e15;
			for(int st = 1; st <= n; st++) {
				if(a[i + st - 1] != a[j + st - 1])
					break;
				eq[i][j][st] = 1;
			}
		}
	}
	for(int k = 1; k <= n; k++) {
		for(int i = 0; i + k - 1 < n; i++) {
			dp[i][i + k - 1] = min(dp[i][i + k - 1], A * k + B);
			for(int j = 0; j < n; j++) {
				for(int z = j; z <= n; z++) {
					dp2[z] = 1e15;	
				}
				dp2[j] = dp[i][i + k - 1];
				for(int z = j; z < n; z++) {
					if(eq[i][z][k])
						dp2[z + k] = min(dp2[z + k], dp2[z] + C);
					dp2[z + 1] = min(dp2[z + 1], dp2[z] + A);
				}
				for(int z = j + 1; z <= n; z++) {
					dp[j][z - 1] = min(dp[j][z - 1], dp2[z] + B); 
				}
		 	}
    	}
    }
    cout << dp[0][n - 1] - B;
}

Subtask #1

1.0 / 1.0

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

Subtask #2

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	324 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Runtime error	2 ms	448 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	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	320 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	324 KB	Output is correct
21	Correct	2 ms	324 KB	Output is correct
22	Correct	2 ms	340 KB	Output is correct
23	Correct	2 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	320 KB	Output is correct
27	Correct	2 ms	340 KB	Output is correct
28	Correct	2 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	1 ms	324 KB	Output is correct
31	Correct	2 ms	340 KB	Output is correct
32	Correct	1 ms	340 KB	Output is correct
33	Correct	2 ms	340 KB	Output is correct
34	Correct	1 ms	212 KB	Output is correct
35	Correct	0 ms	212 KB	Output is correct
36	Correct	1 ms	212 KB	Output is correct
37	Correct	1 ms	340 KB	Output is correct
38	Correct	1 ms	212 KB	Output is correct
39	Correct	2 ms	340 KB	Output is correct

Subtask #4

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	320 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	324 KB	Output is correct
21	Correct	2 ms	324 KB	Output is correct
22	Correct	2 ms	340 KB	Output is correct
23	Correct	2 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	320 KB	Output is correct
27	Correct	2 ms	340 KB	Output is correct
28	Correct	2 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	1 ms	324 KB	Output is correct
31	Correct	2 ms	340 KB	Output is correct
32	Correct	1 ms	340 KB	Output is correct
33	Correct	2 ms	340 KB	Output is correct
34	Correct	1 ms	212 KB	Output is correct
35	Correct	0 ms	212 KB	Output is correct
36	Correct	1 ms	212 KB	Output is correct
37	Correct	1 ms	340 KB	Output is correct
38	Correct	1 ms	212 KB	Output is correct
39	Correct	2 ms	340 KB	Output is correct
40	Runtime error	1 ms	456 KB	Execution killed with signal 11
41	Halted	0 ms	0 KB	-

Subtask #5

0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	320 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	1 ms	324 KB	Output is correct
21	Correct	2 ms	324 KB	Output is correct
22	Correct	2 ms	340 KB	Output is correct
23	Correct	2 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	320 KB	Output is correct
27	Correct	2 ms	340 KB	Output is correct
28	Correct	2 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	1 ms	324 KB	Output is correct
31	Correct	2 ms	340 KB	Output is correct
32	Correct	1 ms	340 KB	Output is correct
33	Correct	2 ms	340 KB	Output is correct
34	Correct	1 ms	212 KB	Output is correct
35	Correct	0 ms	212 KB	Output is correct
36	Correct	1 ms	212 KB	Output is correct
37	Correct	1 ms	340 KB	Output is correct
38	Correct	1 ms	212 KB	Output is correct
39	Correct	2 ms	340 KB	Output is correct
40	Runtime error	1 ms	456 KB	Execution killed with signal 11
41	Halted	0 ms	0 KB	-

Subtask #6

0 / 38.0

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