oj.uz

Submission #998573

# Submission time Handle Problem Language Result Execution time Memory
998573 2024-06-14T08:59:04 Z Sharky Copy and Paste 3 (JOI22_copypaste3) C++17
100 / 100
 947 ms 160888 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 2502;
const int B = 5000011;
const int M1 = 1000000007;
const int M2 = 998244353;

int prv[N][N], nxt[N][N], h1[N][N], h2[N][N], dp[N][N];

int cv(char c) { return (c - 'a' + 1); }
bool same(int l, int r, int x) {
    return (h1[l][l + x] == h1[r][r + x] && h2[l][l + x] == h2[r][r + x]);
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, a, b, c;
    string s;
    cin >> n >> s >> a >> b >> c;
    s = "?" + s;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) dp[i][j] = 1e18;
    for (int i = 1; i <= n; i++) {
        h1[i][i] = h2[i][i] = cv(s[i]);
        dp[i][i] = a;
    }
    for (int itvl = 1; itvl <= n - 1; itvl++) {
        for (int i = 1; i + itvl <= n; i++) {
            int j = i + itvl;
            h1[i][j] = (h1[i][j-1] * B + cv(s[j])) % M1;
            h2[i][j] = (h2[i][j-1] * B + cv(s[j])) % M2;
        }
    }
    for (int itvl = 0; itvl <= n - 1; itvl++) {
        vector<pair<int, int>> h;
        vector<vector<int>> posi(n+1);
        for (int i = 1; i + itvl <= n; i++) h.push_back({h1[i][i + itvl], h2[i][i + itvl]});
        sort(h.begin(), h.end());
        h.erase(unique(h.begin(), h.end()), h.end());
        int hi = 0;
        for (int i = 1; i + itvl <= n; i++) {
            pair<int, int> p = {h1[i][i + itvl], h2[i][i + itvl]};
            int disc = lower_bound(h.begin(), h.end(), p) - h.begin() + 1;
            hi = max(hi, disc);
            posi[disc].push_back(i);
        }
        for (int i = 1; i <= hi; i++) {
            auto& v = posi[i];
            int ptr = 0;
            for (int j = 1; j < v.size(); j++) {
                while (ptr + 1 < j && v[ptr + 1] + itvl < v[j]) ptr++;
                if (v[ptr] + itvl < v[j]) prv[v[j]][v[j] + itvl] = v[ptr];
            }
            ptr = v.size() - 1;
            for (int j = v.size() - 2; j >= 0; j--) {
                while (ptr - 1 > j && v[j] + itvl < v[ptr - 1]) ptr--;
                if (v[j] + itvl < v[ptr]) nxt[v[j]][v[j] + itvl] = v[ptr];
            }
        }
    }
    for (int itvl = 0; itvl <= n - 1; itvl++) {
        for (int i = 1; i + itvl <= n; i++) {
            int j = i, val = dp[i][j + itvl] + b + c;
            while (nxt[j][j + itvl]) {
                int par = j + itvl;
                j = nxt[j][j + itvl];
                val = (j - par - 1) * a + val + c;
                dp[i][j + itvl] = min(dp[i][j + itvl], val);
            }
            j = i;
            val = dp[i][i + itvl] + b + c;
            while (prv[j][j + itvl]) {
                int par = j;
                j = prv[j][j + itvl];
                val = (par - (j + itvl) - 1) * a + val + c;
                dp[j][i + itvl] = min(dp[j][i + itvl], val);
            }
            if (i > 1) dp[i - 1][i + itvl] = min(dp[i - 1][i + itvl], dp[i][i + itvl] + a);
            if (i + itvl < n) dp[i][i + itvl + 1] = min(dp[i][i + itvl + 1], dp[i][i + itvl] + a);
        }
    }
    cout << dp[1][n] << '\n';
}

Compilation message

copypaste3.cpp: In function 'int32_t main()':
copypaste3.cpp:52:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             for (int j = 1; j < v.size(); j++) {
      |                             ~~^~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 49496 KB Output is correct
2 Correct 17 ms 49496 KB Output is correct
3 Correct 18 ms 49304 KB Output is correct
4 Correct 17 ms 49348 KB Output is correct
5 Correct 19 ms 49448 KB Output is correct
6 Correct 18 ms 49500 KB Output is correct
7 Correct 18 ms 49500 KB Output is correct
8 Correct 16 ms 49500 KB Output is correct
9 Correct 16 ms 49364 KB Output is correct
10 Correct 19 ms 49496 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 49496 KB Output is correct
2 Correct 17 ms 49500 KB Output is correct
3 Correct 275 ms 118072 KB Output is correct
4 Correct 316 ms 127060 KB Output is correct
5 Correct 411 ms 137280 KB Output is correct
6 Correct 460 ms 148656 KB Output is correct
7 Correct 556 ms 160888 KB Output is correct
8 Correct 565 ms 160888 KB Output is correct
9 Correct 562 ms 160844 KB Output is correct
10 Correct 17 ms 49244 KB Output is correct
11 Correct 18 ms 49244 KB Output is correct
12 Correct 19 ms 49496 KB Output is correct
13 Correct 19 ms 49496 KB Output is correct
14 Correct 17 ms 49456 KB Output is correct
15 Correct 18 ms 49500 KB Output is correct
16 Correct 17 ms 49756 KB Output is correct
17 Correct 17 ms 49420 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 49496 KB Output is correct
2 Correct 17 ms 49496 KB Output is correct
3 Correct 18 ms 49304 KB Output is correct
4 Correct 17 ms 49348 KB Output is correct
5 Correct 19 ms 49448 KB Output is correct
6 Correct 18 ms 49500 KB Output is correct
7 Correct 18 ms 49500 KB Output is correct
8 Correct 16 ms 49500 KB Output is correct
9 Correct 16 ms 49364 KB Output is correct
10 Correct 19 ms 49496 KB Output is correct
11 Correct 18 ms 49496 KB Output is correct
12 Correct 17 ms 49500 KB Output is correct
13 Correct 18 ms 49500 KB Output is correct
14 Correct 18 ms 49500 KB Output is correct
15 Correct 17 ms 49612 KB Output is correct
16 Correct 17 ms 49500 KB Output is correct
17 Correct 20 ms 49420 KB Output is correct
18 Correct 17 ms 49244 KB Output is correct
19 Correct 17 ms 49500 KB Output is correct
20 Correct 18 ms 49496 KB Output is correct
21 Correct 17 ms 49800 KB Output is correct
22 Correct 17 ms 49896 KB Output is correct
23 Correct 17 ms 49752 KB Output is correct
24 Correct 17 ms 49756 KB Output is correct
25 Correct 17 ms 49756 KB Output is correct
26 Correct 20 ms 49612 KB Output is correct
27 Correct 18 ms 49756 KB Output is correct
28 Correct 18 ms 49752 KB Output is correct
29 Correct 17 ms 49896 KB Output is correct
30 Correct 17 ms 49724 KB Output is correct
31 Correct 17 ms 49756 KB Output is correct
32 Correct 18 ms 49904 KB Output is correct
33 Correct 20 ms 49756 KB Output is correct
34 Correct 18 ms 49436 KB Output is correct
35 Correct 18 ms 49500 KB Output is correct
36 Correct 17 ms 49500 KB Output is correct
37 Correct 16 ms 49500 KB Output is correct
38 Correct 17 ms 49496 KB Output is correct
39 Correct 17 ms 49816 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 49496 KB Output is correct
2 Correct 17 ms 49496 KB Output is correct
3 Correct 18 ms 49304 KB Output is correct
4 Correct 17 ms 49348 KB Output is correct
5 Correct 19 ms 49448 KB Output is correct
6 Correct 18 ms 49500 KB Output is correct
7 Correct 18 ms 49500 KB Output is correct
8 Correct 16 ms 49500 KB Output is correct
9 Correct 16 ms 49364 KB Output is correct
10 Correct 19 ms 49496 KB Output is correct
11 Correct 18 ms 49496 KB Output is correct
12 Correct 17 ms 49500 KB Output is correct
13 Correct 18 ms 49500 KB Output is correct
14 Correct 18 ms 49500 KB Output is correct
15 Correct 17 ms 49612 KB Output is correct
16 Correct 17 ms 49500 KB Output is correct
17 Correct 20 ms 49420 KB Output is correct
18 Correct 17 ms 49244 KB Output is correct
19 Correct 17 ms 49500 KB Output is correct
20 Correct 18 ms 49496 KB Output is correct
21 Correct 17 ms 49800 KB Output is correct
22 Correct 17 ms 49896 KB Output is correct
23 Correct 17 ms 49752 KB Output is correct
24 Correct 17 ms 49756 KB Output is correct
25 Correct 17 ms 49756 KB Output is correct
26 Correct 20 ms 49612 KB Output is correct
27 Correct 18 ms 49756 KB Output is correct
28 Correct 18 ms 49752 KB Output is correct
29 Correct 17 ms 49896 KB Output is correct
30 Correct 17 ms 49724 KB Output is correct
31 Correct 17 ms 49756 KB Output is correct
32 Correct 18 ms 49904 KB Output is correct
33 Correct 20 ms 49756 KB Output is correct
34 Correct 18 ms 49436 KB Output is correct
35 Correct 18 ms 49500 KB Output is correct
36 Correct 17 ms 49500 KB Output is correct
37 Correct 16 ms 49500 KB Output is correct
38 Correct 17 ms 49496 KB Output is correct
39 Correct 17 ms 49816 KB Output is correct
40 Correct 18 ms 50776 KB Output is correct
41 Correct 20 ms 52908 KB Output is correct
42 Correct 21 ms 52828 KB Output is correct
43 Correct 21 ms 52760 KB Output is correct
44 Correct 21 ms 52856 KB Output is correct
45 Correct 21 ms 52828 KB Output is correct
46 Correct 21 ms 52792 KB Output is correct
47 Correct 20 ms 52824 KB Output is correct
48 Correct 21 ms 52828 KB Output is correct
49 Correct 21 ms 52896 KB Output is correct
50 Correct 21 ms 52824 KB Output is correct
51 Correct 20 ms 53084 KB Output is correct
52 Correct 21 ms 53084 KB Output is correct
53 Correct 21 ms 52564 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 49496 KB Output is correct
2 Correct 17 ms 49496 KB Output is correct
3 Correct 18 ms 49304 KB Output is correct
4 Correct 17 ms 49348 KB Output is correct
5 Correct 19 ms 49448 KB Output is correct
6 Correct 18 ms 49500 KB Output is correct
7 Correct 18 ms 49500 KB Output is correct
8 Correct 16 ms 49500 KB Output is correct
9 Correct 16 ms 49364 KB Output is correct
10 Correct 19 ms 49496 KB Output is correct
11 Correct 18 ms 49496 KB Output is correct
12 Correct 17 ms 49500 KB Output is correct
13 Correct 18 ms 49500 KB Output is correct
14 Correct 18 ms 49500 KB Output is correct
15 Correct 17 ms 49612 KB Output is correct
16 Correct 17 ms 49500 KB Output is correct
17 Correct 20 ms 49420 KB Output is correct
18 Correct 17 ms 49244 KB Output is correct
19 Correct 17 ms 49500 KB Output is correct
20 Correct 18 ms 49496 KB Output is correct
21 Correct 17 ms 49800 KB Output is correct
22 Correct 17 ms 49896 KB Output is correct
23 Correct 17 ms 49752 KB Output is correct
24 Correct 17 ms 49756 KB Output is correct
25 Correct 17 ms 49756 KB Output is correct
26 Correct 20 ms 49612 KB Output is correct
27 Correct 18 ms 49756 KB Output is correct
28 Correct 18 ms 49752 KB Output is correct
29 Correct 17 ms 49896 KB Output is correct
30 Correct 17 ms 49724 KB Output is correct
31 Correct 17 ms 49756 KB Output is correct
32 Correct 18 ms 49904 KB Output is correct
33 Correct 20 ms 49756 KB Output is correct
34 Correct 18 ms 49436 KB Output is correct
35 Correct 18 ms 49500 KB Output is correct
36 Correct 17 ms 49500 KB Output is correct
37 Correct 16 ms 49500 KB Output is correct
38 Correct 17 ms 49496 KB Output is correct
39 Correct 17 ms 49816 KB Output is correct
40 Correct 18 ms 50776 KB Output is correct
41 Correct 20 ms 52908 KB Output is correct
42 Correct 21 ms 52828 KB Output is correct
43 Correct 21 ms 52760 KB Output is correct
44 Correct 21 ms 52856 KB Output is correct
45 Correct 21 ms 52828 KB Output is correct
46 Correct 21 ms 52792 KB Output is correct
47 Correct 20 ms 52824 KB Output is correct
48 Correct 21 ms 52828 KB Output is correct
49 Correct 21 ms 52896 KB Output is correct
50 Correct 21 ms 52824 KB Output is correct
51 Correct 20 ms 53084 KB Output is correct
52 Correct 21 ms 53084 KB Output is correct
53 Correct 21 ms 52564 KB Output is correct
54 Correct 39 ms 58124 KB Output is correct
55 Correct 79 ms 77140 KB Output is correct
56 Correct 114 ms 73628 KB Output is correct
57 Correct 110 ms 73396 KB Output is correct
58 Correct 107 ms 73508 KB Output is correct
59 Correct 104 ms 73304 KB Output is correct
60 Correct 104 ms 73300 KB Output is correct
61 Correct 108 ms 76176 KB Output is correct
62 Correct 76 ms 77140 KB Output is correct
63 Correct 107 ms 75092 KB Output is correct
64 Correct 111 ms 75092 KB Output is correct
65 Correct 119 ms 76736 KB Output is correct
66 Correct 121 ms 76624 KB Output is correct
67 Correct 105 ms 73296 KB Output is correct

Subtask #6
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 49496 KB Output is correct
2 Correct 17 ms 49496 KB Output is correct
3 Correct 18 ms 49304 KB Output is correct
4 Correct 17 ms 49348 KB Output is correct
5 Correct 19 ms 49448 KB Output is correct
6 Correct 18 ms 49500 KB Output is correct
7 Correct 18 ms 49500 KB Output is correct
8 Correct 16 ms 49500 KB Output is correct
9 Correct 16 ms 49364 KB Output is correct
10 Correct 19 ms 49496 KB Output is correct
11 Correct 19 ms 49496 KB Output is correct
12 Correct 17 ms 49500 KB Output is correct
13 Correct 275 ms 118072 KB Output is correct
14 Correct 316 ms 127060 KB Output is correct
15 Correct 411 ms 137280 KB Output is correct
16 Correct 460 ms 148656 KB Output is correct
17 Correct 556 ms 160888 KB Output is correct
18 Correct 565 ms 160888 KB Output is correct
19 Correct 562 ms 160844 KB Output is correct
20 Correct 17 ms 49244 KB Output is correct
21 Correct 18 ms 49244 KB Output is correct
22 Correct 19 ms 49496 KB Output is correct
23 Correct 19 ms 49496 KB Output is correct
24 Correct 17 ms 49456 KB Output is correct
25 Correct 18 ms 49500 KB Output is correct
26 Correct 17 ms 49756 KB Output is correct
27 Correct 17 ms 49420 KB Output is correct
28 Correct 18 ms 49496 KB Output is correct
29 Correct 17 ms 49500 KB Output is correct
30 Correct 18 ms 49500 KB Output is correct
31 Correct 18 ms 49500 KB Output is correct
32 Correct 17 ms 49612 KB Output is correct
33 Correct 17 ms 49500 KB Output is correct
34 Correct 20 ms 49420 KB Output is correct
35 Correct 17 ms 49244 KB Output is correct
36 Correct 17 ms 49500 KB Output is correct
37 Correct 18 ms 49496 KB Output is correct
38 Correct 17 ms 49800 KB Output is correct
39 Correct 17 ms 49896 KB Output is correct
40 Correct 17 ms 49752 KB Output is correct
41 Correct 17 ms 49756 KB Output is correct
42 Correct 17 ms 49756 KB Output is correct
43 Correct 20 ms 49612 KB Output is correct
44 Correct 18 ms 49756 KB Output is correct
45 Correct 18 ms 49752 KB Output is correct
46 Correct 17 ms 49896 KB Output is correct
47 Correct 17 ms 49724 KB Output is correct
48 Correct 17 ms 49756 KB Output is correct
49 Correct 18 ms 49904 KB Output is correct
50 Correct 20 ms 49756 KB Output is correct
51 Correct 18 ms 49436 KB Output is correct
52 Correct 18 ms 49500 KB Output is correct
53 Correct 17 ms 49500 KB Output is correct
54 Correct 16 ms 49500 KB Output is correct
55 Correct 17 ms 49496 KB Output is correct
56 Correct 17 ms 49816 KB Output is correct
57 Correct 18 ms 50776 KB Output is correct
58 Correct 20 ms 52908 KB Output is correct
59 Correct 21 ms 52828 KB Output is correct
60 Correct 21 ms 52760 KB Output is correct
61 Correct 21 ms 52856 KB Output is correct
62 Correct 21 ms 52828 KB Output is correct
63 Correct 21 ms 52792 KB Output is correct
64 Correct 20 ms 52824 KB Output is correct
65 Correct 21 ms 52828 KB Output is correct
66 Correct 21 ms 52896 KB Output is correct
67 Correct 21 ms 52824 KB Output is correct
68 Correct 20 ms 53084 KB Output is correct
69 Correct 21 ms 53084 KB Output is correct
70 Correct 21 ms 52564 KB Output is correct
71 Correct 39 ms 58124 KB Output is correct
72 Correct 79 ms 77140 KB Output is correct
73 Correct 114 ms 73628 KB Output is correct
74 Correct 110 ms 73396 KB Output is correct
75 Correct 107 ms 73508 KB Output is correct
76 Correct 104 ms 73304 KB Output is correct
77 Correct 104 ms 73300 KB Output is correct
78 Correct 108 ms 76176 KB Output is correct
79 Correct 76 ms 77140 KB Output is correct
80 Correct 107 ms 75092 KB Output is correct
81 Correct 111 ms 75092 KB Output is correct
82 Correct 119 ms 76736 KB Output is correct
83 Correct 121 ms 76624 KB Output is correct
84 Correct 105 ms 73296 KB Output is correct
85 Correct 285 ms 94800 KB Output is correct
86 Correct 695 ms 137044 KB Output is correct
87 Correct 659 ms 136868 KB Output is correct
88 Correct 626 ms 136940 KB Output is correct
89 Correct 620 ms 136788 KB Output is correct
90 Correct 606 ms 136712 KB Output is correct
91 Correct 568 ms 160340 KB Output is correct
92 Correct 539 ms 160852 KB Output is correct
93 Correct 632 ms 151472 KB Output is correct
94 Correct 660 ms 148700 KB Output is correct
95 Correct 947 ms 158188 KB Output is correct
96 Correct 938 ms 158000 KB Output is correct
97 Correct 608 ms 136708 KB Output is correct