oj.uz

Submission #972713

# Submission time Handle Problem Language Result Execution time Memory
972713 2024-05-01T04:19:05 Z happy_node Copy and Paste 3 (JOI22_copypaste3) C++17
62 / 100
 409 ms 161732 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MX=2505;

int N, A, B, C;
string s;
ll dp[MX][MX];

const ll P=1e9+93, mod=2'147'483'647;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll hsh[MX][MX], pw[MX], key[MX];

int nxt[MX][MX];

bool ok(int a, int b, int l, int r) {
	if(l<=b) return false;
	return hsh[a][b]==hsh[l][r];
}

vector<pair<ll,ll>> v[MX];

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	for(int i=0;i<MX;i++)
		for(int j=i;j<MX;j++)
			dp[i][j]=2e18;

	pw[0]=1;
	for(int i=1;i<MX;i++) pw[i]=pw[i-1]*P%mod;

	cin>>N;
	cin>>s;
	cin>>A>>B>>C;

	s='#'+s;

	for(int c=0;c<26;c++) key[c]=rng()%mod;

	for(int l=1;l<=N;l++) {
		for(int r=l;r<=N;r++) {
			int p=r-l+1;
			hsh[l][r]=hsh[l][r-1]+pw[p]*(key[s[r]-'a'])%mod;
			hsh[l][r]%=mod;
			v[p].push_back({hsh[l][r],l});
		}
	}

	for(int i=1;i<=N;i++) {
		sort(v[i].begin(),v[i].end());

		int k=0;
		for(int j=0;j<v[i].size();j++) {
			if(k<j) k++;

			while(k<v[i].size() && v[i][k+1].first==v[i][k].first 
				&& v[i][k].second<v[i][j].second+i) {
				k++;
			}	
			if(k>=v[i].size()) {
				nxt[v[i][j].second][v[i][j].second+i-1]= -1;
				continue;
			}
			if(v[i][k].second<v[i][j].second+i) {
				nxt[v[i][j].second][v[i][j].second+i-1]= -1;
				continue;
			}
			nxt[v[i][j].second][v[i][j].second+i-1]=v[i][k].second;
		}
	}

	for(int l=N;l>0;l--) {
		for(int r=l;r<=N;r++) {
			dp[l][r]=min(dp[l][r],dp[l][r-1]+A);

			ll k=nxt[l][r], p=r-l+1, z=1;

			while(k!=-1) {
				z++;
				ll len=k+p-1-l+1;
				dp[l][k+p-1]=min(dp[l][k+p-1],dp[l][r]+z*C+B+(len-p*z)*A);
				k=nxt[k][k+p-1];
			}

			dp[l-1][r]=min(dp[l-1][r],dp[l][r]+A);
		}
	}

	cout<<dp[1][N]<<'\n';

}

Compilation message

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:58:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int j=0;j<v[i].size();j++) {
      |               ~^~~~~~~~~~~~
copypaste3.cpp:61:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |    while(k<v[i].size() && v[i][k+1].first==v[i][k].first
      |          ~^~~~~~~~~~~~
copypaste3.cpp:65:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |    if(k>=v[i].size()) {
      |       ~^~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 43352 KB Output is correct
2 Correct 7 ms 43356 KB Output is correct
3 Correct 7 ms 42332 KB Output is correct
4 Correct 7 ms 43356 KB Output is correct
5 Correct 7 ms 43356 KB Output is correct
6 Correct 8 ms 42332 KB Output is correct
7 Correct 7 ms 43356 KB Output is correct
8 Correct 7 ms 43332 KB Output is correct
9 Correct 7 ms 43352 KB Output is correct
10 Correct 7 ms 43356 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 43356 KB Output is correct
2 Correct 7 ms 43356 KB Output is correct
3 Correct 189 ms 110620 KB Output is correct
4 Correct 243 ms 119524 KB Output is correct
5 Correct 287 ms 132840 KB Output is correct
6 Correct 342 ms 145872 KB Output is correct
7 Correct 408 ms 161340 KB Output is correct
8 Correct 409 ms 161620 KB Output is correct
9 Correct 404 ms 161352 KB Output is correct
10 Correct 8 ms 43352 KB Output is correct
11 Correct 7 ms 42332 KB Output is correct
12 Correct 8 ms 42332 KB Output is correct
13 Correct 7 ms 43356 KB Output is correct
14 Correct 7 ms 42332 KB Output is correct
15 Correct 7 ms 43356 KB Output is correct
16 Correct 8 ms 42440 KB Output is correct
17 Correct 7 ms 43356 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 43352 KB Output is correct
2 Correct 7 ms 43356 KB Output is correct
3 Correct 7 ms 42332 KB Output is correct
4 Correct 7 ms 43356 KB Output is correct
5 Correct 7 ms 43356 KB Output is correct
6 Correct 8 ms 42332 KB Output is correct
7 Correct 7 ms 43356 KB Output is correct
8 Correct 7 ms 43332 KB Output is correct
9 Correct 7 ms 43352 KB Output is correct
10 Correct 7 ms 43356 KB Output is correct
11 Correct 7 ms 43356 KB Output is correct
12 Correct 7 ms 42380 KB Output is correct
13 Correct 8 ms 43352 KB Output is correct
14 Correct 7 ms 43352 KB Output is correct
15 Correct 8 ms 43356 KB Output is correct
16 Correct 7 ms 42332 KB Output is correct
17 Correct 8 ms 43612 KB Output is correct
18 Correct 7 ms 43356 KB Output is correct
19 Correct 7 ms 43356 KB Output is correct
20 Correct 8 ms 42328 KB Output is correct
21 Correct 7 ms 42588 KB Output is correct
22 Correct 8 ms 42424 KB Output is correct
23 Correct 7 ms 43612 KB Output is correct
24 Correct 8 ms 42620 KB Output is correct
25 Correct 7 ms 43864 KB Output is correct
26 Correct 7 ms 43612 KB Output is correct
27 Correct 7 ms 43612 KB Output is correct
28 Correct 7 ms 42588 KB Output is correct
29 Correct 7 ms 43544 KB Output is correct
30 Correct 8 ms 42588 KB Output is correct
31 Correct 7 ms 43612 KB Output is correct
32 Correct 8 ms 43612 KB Output is correct
33 Correct 9 ms 42584 KB Output is correct
34 Correct 7 ms 43352 KB Output is correct
35 Correct 8 ms 43328 KB Output is correct
36 Correct 7 ms 43356 KB Output is correct
37 Correct 7 ms 43312 KB Output is correct
38 Correct 7 ms 43356 KB Output is correct
39 Correct 7 ms 43612 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 43352 KB Output is correct
2 Correct 7 ms 43356 KB Output is correct
3 Correct 7 ms 42332 KB Output is correct
4 Correct 7 ms 43356 KB Output is correct
5 Correct 7 ms 43356 KB Output is correct
6 Correct 8 ms 42332 KB Output is correct
7 Correct 7 ms 43356 KB Output is correct
8 Correct 7 ms 43332 KB Output is correct
9 Correct 7 ms 43352 KB Output is correct
10 Correct 7 ms 43356 KB Output is correct
11 Correct 7 ms 43356 KB Output is correct
12 Correct 7 ms 42380 KB Output is correct
13 Correct 8 ms 43352 KB Output is correct
14 Correct 7 ms 43352 KB Output is correct
15 Correct 8 ms 43356 KB Output is correct
16 Correct 7 ms 42332 KB Output is correct
17 Correct 8 ms 43612 KB Output is correct
18 Correct 7 ms 43356 KB Output is correct
19 Correct 7 ms 43356 KB Output is correct
20 Correct 8 ms 42328 KB Output is correct
21 Correct 7 ms 42588 KB Output is correct
22 Correct 8 ms 42424 KB Output is correct
23 Correct 7 ms 43612 KB Output is correct
24 Correct 8 ms 42620 KB Output is correct
25 Correct 7 ms 43864 KB Output is correct
26 Correct 7 ms 43612 KB Output is correct
27 Correct 7 ms 43612 KB Output is correct
28 Correct 7 ms 42588 KB Output is correct
29 Correct 7 ms 43544 KB Output is correct
30 Correct 8 ms 42588 KB Output is correct
31 Correct 7 ms 43612 KB Output is correct
32 Correct 8 ms 43612 KB Output is correct
33 Correct 9 ms 42584 KB Output is correct
34 Correct 7 ms 43352 KB Output is correct
35 Correct 8 ms 43328 KB Output is correct
36 Correct 7 ms 43356 KB Output is correct
37 Correct 7 ms 43312 KB Output is correct
38 Correct 7 ms 43356 KB Output is correct
39 Correct 7 ms 43612 KB Output is correct
40 Correct 8 ms 44124 KB Output is correct
41 Correct 9 ms 45588 KB Output is correct
42 Correct 9 ms 45660 KB Output is correct
43 Correct 9 ms 45660 KB Output is correct
44 Correct 10 ms 44636 KB Output is correct
45 Correct 9 ms 46916 KB Output is correct
46 Correct 9 ms 43860 KB Output is correct
47 Correct 9 ms 45660 KB Output is correct
48 Correct 9 ms 45660 KB Output is correct
49 Correct 10 ms 45660 KB Output is correct
50 Correct 9 ms 45732 KB Output is correct
51 Correct 9 ms 44636 KB Output is correct
52 Correct 10 ms 45660 KB Output is correct
53 Correct 9 ms 44632 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 43352 KB Output is correct
2 Correct 7 ms 43356 KB Output is correct
3 Correct 7 ms 42332 KB Output is correct
4 Correct 7 ms 43356 KB Output is correct
5 Correct 7 ms 43356 KB Output is correct
6 Correct 8 ms 42332 KB Output is correct
7 Correct 7 ms 43356 KB Output is correct
8 Correct 7 ms 43332 KB Output is correct
9 Correct 7 ms 43352 KB Output is correct
10 Correct 7 ms 43356 KB Output is correct
11 Correct 7 ms 43356 KB Output is correct
12 Correct 7 ms 42380 KB Output is correct
13 Correct 8 ms 43352 KB Output is correct
14 Correct 7 ms 43352 KB Output is correct
15 Correct 8 ms 43356 KB Output is correct
16 Correct 7 ms 42332 KB Output is correct
17 Correct 8 ms 43612 KB Output is correct
18 Correct 7 ms 43356 KB Output is correct
19 Correct 7 ms 43356 KB Output is correct
20 Correct 8 ms 42328 KB Output is correct
21 Correct 7 ms 42588 KB Output is correct
22 Correct 8 ms 42424 KB Output is correct
23 Correct 7 ms 43612 KB Output is correct
24 Correct 8 ms 42620 KB Output is correct
25 Correct 7 ms 43864 KB Output is correct
26 Correct 7 ms 43612 KB Output is correct
27 Correct 7 ms 43612 KB Output is correct
28 Correct 7 ms 42588 KB Output is correct
29 Correct 7 ms 43544 KB Output is correct
30 Correct 8 ms 42588 KB Output is correct
31 Correct 7 ms 43612 KB Output is correct
32 Correct 8 ms 43612 KB Output is correct
33 Correct 9 ms 42584 KB Output is correct
34 Correct 7 ms 43352 KB Output is correct
35 Correct 8 ms 43328 KB Output is correct
36 Correct 7 ms 43356 KB Output is correct
37 Correct 7 ms 43312 KB Output is correct
38 Correct 7 ms 43356 KB Output is correct
39 Correct 7 ms 43612 KB Output is correct
40 Correct 8 ms 44124 KB Output is correct
41 Correct 9 ms 45588 KB Output is correct
42 Correct 9 ms 45660 KB Output is correct
43 Correct 9 ms 45660 KB Output is correct
44 Correct 10 ms 44636 KB Output is correct
45 Correct 9 ms 46916 KB Output is correct
46 Correct 9 ms 43860 KB Output is correct
47 Correct 9 ms 45660 KB Output is correct
48 Correct 9 ms 45660 KB Output is correct
49 Correct 10 ms 45660 KB Output is correct
50 Correct 9 ms 45732 KB Output is correct
51 Correct 9 ms 44636 KB Output is correct
52 Correct 10 ms 45660 KB Output is correct
53 Correct 9 ms 44632 KB Output is correct
54 Correct 16 ms 50268 KB Output is correct
55 Correct 53 ms 67492 KB Output is correct
56 Correct 52 ms 67432 KB Output is correct
57 Correct 48 ms 66388 KB Output is correct
58 Correct 47 ms 67608 KB Output is correct
59 Correct 45 ms 67408 KB Output is correct
60 Correct 47 ms 67548 KB Output is correct
61 Correct 52 ms 66412 KB Output is correct
62 Correct 55 ms 66540 KB Output is correct
63 Correct 49 ms 67408 KB Output is correct
64 Correct 49 ms 67408 KB Output is correct
65 Correct 58 ms 67660 KB Output is correct
66 Correct 56 ms 67408 KB Output is correct
67 Correct 47 ms 66352 KB Output is correct

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 43352 KB Output is correct
2 Correct 7 ms 43356 KB Output is correct
3 Correct 7 ms 42332 KB Output is correct
4 Correct 7 ms 43356 KB Output is correct
5 Correct 7 ms 43356 KB Output is correct
6 Correct 8 ms 42332 KB Output is correct
7 Correct 7 ms 43356 KB Output is correct
8 Correct 7 ms 43332 KB Output is correct
9 Correct 7 ms 43352 KB Output is correct
10 Correct 7 ms 43356 KB Output is correct
11 Correct 7 ms 43356 KB Output is correct
12 Correct 7 ms 43356 KB Output is correct
13 Correct 189 ms 110620 KB Output is correct
14 Correct 243 ms 119524 KB Output is correct
15 Correct 287 ms 132840 KB Output is correct
16 Correct 342 ms 145872 KB Output is correct
17 Correct 408 ms 161340 KB Output is correct
18 Correct 409 ms 161620 KB Output is correct
19 Correct 404 ms 161352 KB Output is correct
20 Correct 8 ms 43352 KB Output is correct
21 Correct 7 ms 42332 KB Output is correct
22 Correct 8 ms 42332 KB Output is correct
23 Correct 7 ms 43356 KB Output is correct
24 Correct 7 ms 42332 KB Output is correct
25 Correct 7 ms 43356 KB Output is correct
26 Correct 8 ms 42440 KB Output is correct
27 Correct 7 ms 43356 KB Output is correct
28 Correct 7 ms 43356 KB Output is correct
29 Correct 7 ms 42380 KB Output is correct
30 Correct 8 ms 43352 KB Output is correct
31 Correct 7 ms 43352 KB Output is correct
32 Correct 8 ms 43356 KB Output is correct
33 Correct 7 ms 42332 KB Output is correct
34 Correct 8 ms 43612 KB Output is correct
35 Correct 7 ms 43356 KB Output is correct
36 Correct 7 ms 43356 KB Output is correct
37 Correct 8 ms 42328 KB Output is correct
38 Correct 7 ms 42588 KB Output is correct
39 Correct 8 ms 42424 KB Output is correct
40 Correct 7 ms 43612 KB Output is correct
41 Correct 8 ms 42620 KB Output is correct
42 Correct 7 ms 43864 KB Output is correct
43 Correct 7 ms 43612 KB Output is correct
44 Correct 7 ms 43612 KB Output is correct
45 Correct 7 ms 42588 KB Output is correct
46 Correct 7 ms 43544 KB Output is correct
47 Correct 8 ms 42588 KB Output is correct
48 Correct 7 ms 43612 KB Output is correct
49 Correct 8 ms 43612 KB Output is correct
50 Correct 9 ms 42584 KB Output is correct
51 Correct 7 ms 43352 KB Output is correct
52 Correct 8 ms 43328 KB Output is correct
53 Correct 7 ms 43356 KB Output is correct
54 Correct 7 ms 43312 KB Output is correct
55 Correct 7 ms 43356 KB Output is correct
56 Correct 7 ms 43612 KB Output is correct
57 Correct 8 ms 44124 KB Output is correct
58 Correct 9 ms 45588 KB Output is correct
59 Correct 9 ms 45660 KB Output is correct
60 Correct 9 ms 45660 KB Output is correct
61 Correct 10 ms 44636 KB Output is correct
62 Correct 9 ms 46916 KB Output is correct
63 Correct 9 ms 43860 KB Output is correct
64 Correct 9 ms 45660 KB Output is correct
65 Correct 9 ms 45660 KB Output is correct
66 Correct 10 ms 45660 KB Output is correct
67 Correct 9 ms 45732 KB Output is correct
68 Correct 9 ms 44636 KB Output is correct
69 Correct 10 ms 45660 KB Output is correct
70 Correct 9 ms 44632 KB Output is correct
71 Correct 16 ms 50268 KB Output is correct
72 Correct 53 ms 67492 KB Output is correct
73 Correct 52 ms 67432 KB Output is correct
74 Correct 48 ms 66388 KB Output is correct
75 Correct 47 ms 67608 KB Output is correct
76 Correct 45 ms 67408 KB Output is correct
77 Correct 47 ms 67548 KB Output is correct
78 Correct 52 ms 66412 KB Output is correct
79 Correct 55 ms 66540 KB Output is correct
80 Correct 49 ms 67408 KB Output is correct
81 Correct 49 ms 67408 KB Output is correct
82 Correct 58 ms 67660 KB Output is correct
83 Correct 56 ms 67408 KB Output is correct
84 Correct 47 ms 66352 KB Output is correct
85 Correct 113 ms 97360 KB Output is correct
86 Correct 285 ms 161360 KB Output is correct
87 Correct 276 ms 161732 KB Output is correct
88 Correct 265 ms 160296 KB Output is correct
89 Correct 262 ms 161524 KB Output is correct
90 Incorrect 262 ms 161372 KB Output isn't correct
91 Halted 0 ms 0 KB -