oj.uz

Submission #776755

# Submission time Handle Problem Language Result Execution time Memory
776755 2023-07-08T08:35:15 Z danikoynov Copy and Paste 3 (JOI22_copypaste3) C++14
62 / 100
 3000 ms 894180 KB 
/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}


const int maxn = 2510;
const ll base = 29, inf = 1e18;

int n;
ll a, b, c, h[maxn], pw[maxn];
string s;
vector < int >  occ[maxn * maxn];
ll hs_dp[maxn * maxn], pt[maxn * maxn];
unordered_map < int, int > nxt[maxn * maxn];
ll range_hash[maxn][maxn];
ll get_hash(int i, int j)
{
    return range_hash[i][j];
}

unordered_map < ll, ll > rev;
void solve()
{
    cin >> n >> s >> a >> b >> c;
    s = "#" + s;
    pw[0] = 1;
    for (int i = 1; i <= n; i ++)
    {
        h[i] = h[i - 1] * base + (s[i] - 'a' + 1);
        pw[i] = pw[i - 1] * base;
    }
    vector < ll > cp;
    for (int i = 1; i <= n; i ++)
        for (int j = i; j <= n; j ++)
    {
        range_hash[i][j] = h[j] - h[i - 1] * pw[j - i + 1];
        cp.push_back(range_hash[i][j]);
    }
    sort(cp.begin(), cp.end());
    int cnt = 0;
    for (int i = 0; i < cp.size(); i ++)
    {
        if (i == 0 || cp[i] != cp[i - 1])
            rev[cp[i]] = ++ cnt;
    }

    for (int i = 1; i <= n; i ++)
        for (int j = i; j <= n; j ++)
        range_hash[i][j] = rev[range_hash[i][j]];


    for (int i = n; i > 0; i --)
    {


        for (int p = i; p <= n; p ++)
        {
            ll cur_hs = get_hash(i, p);
            occ[cur_hs].push_back(i);
            /**cout << "hash " << i << " " << p << endl;
            cout << "occurrences: ";
            for (int ds : occ[cur_hs])
                cout << ds << " ";
            cout << endl;*/
            if (occ[cur_hs].size() == 1)
            {
                hs_dp[cur_hs] = hs_dp[get_hash(i + 1, p)] + a;
                nxt[cur_hs][p] = n + 1;
                pt[cur_hs] = -1;
            }
            else
            {
                hs_dp[cur_hs] = min(hs_dp[cur_hs], hs_dp[get_hash(i + 1, p)] + a);
                if (pt[cur_hs] == -1)
                {
                    pt[cur_hs] ++;
                }
                while(occ[cur_hs][pt[cur_hs]] > p)
                    pt[cur_hs] ++;
                pt[cur_hs] --;
                if (pt[cur_hs] == -1)
                    nxt[cur_hs][p] = n + 1;
                else
                    nxt[cur_hs][p] = occ[cur_hs][pt[cur_hs]] + (p - i);
                    ///cout << "step " << i << " " << p << " " << nxt[p][cur_hs] << endl;
            }
        }


        for (int k = i; k <= n; k ++)
        {
            ll clip_hash, clip_len = k - i + 1;
            clip_hash = get_hash(i, k);
            ll cost = hs_dp[clip_hash] + b + c;
            if (occ[get_hash(i, k)].size() < 2)
                break;
            int pos = k, pt = (int)(occ[clip_hash].size()) - 1;
            ///dp[get_hash(i, k)] = min(dp[get_hash(i, k)], cos);
            ///cout << "-------------------" << endl;
            ///cout << i << " " << k << endl;
            while(pos <= n)
            {
                ///cout << pos << " " << cost << endl;
                int to = nxt[clip_hash][pos];
                if (to > n)
                    break;
                cost = cost + (to - pos - clip_len) * a;
                cost = cost + c;
                ///cout << "stop " << occ[clip_hash][pt] << endl;
                ///cost = cost + (occ[clip_hash][pt] - pos) * a;
                ///cost = cost + c;
                pos = to;
                hs_dp[get_hash(i, pos)] = min(hs_dp[get_hash(i, pos)], cost);

                /**int to = pos + clip_len - 1;

                if (to > n)
                {
                    break;
                }

                if (get_hash(pos, to) == clip_hash)
                {

                    cost = cost + c;
                    pos = pos + clip_len;
                    hs_dp[get_hash(i, to)] = min(hs_dp[get_hash(i, to)], cost);
                }
                else
                {
                    pos ++;
                    cost += a;
                }*/
            }

        }
        for (int k = i; k <= n; k ++)
        {
            hs_dp[get_hash(i, k)] = min(hs_dp[get_hash(i, k)], hs_dp[get_hash(i, k - 1)] + a);
        }

    }

    /**for (int i = 1; i <= n; i ++, cout << endl)
        for (int j = i; j <= n; j ++)
            cout << hs_dp[get_hash(i, j)] << " ";*/

    cout << hs_dp[get_hash(1, n)] << endl;


}

int main()
{
    solve();
    return 0;
}

Compilation message

copypaste3.cpp: In function 'void solve()':
copypaste3.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (int i = 0; i < cp.size(); i ++)
      |                     ~~^~~~~~~~~~~
copypaste3.cpp:114:26: warning: unused variable 'pt' [-Wunused-variable]
  114 |             int pos = k, pt = (int)(occ[clip_hash].size()) - 1;
      |                          ^~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 493428 KB Output is correct
2 Correct 205 ms 493388 KB Output is correct
3 Correct 213 ms 493528 KB Output is correct
4 Correct 204 ms 493484 KB Output is correct
5 Correct 213 ms 493432 KB Output is correct
6 Correct 221 ms 493376 KB Output is correct
7 Correct 233 ms 493488 KB Output is correct
8 Correct 210 ms 493488 KB Output is correct
9 Correct 212 ms 493384 KB Output is correct
10 Correct 207 ms 493492 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 493476 KB Output is correct
2 Correct 210 ms 493420 KB Output is correct
3 Correct 1380 ms 608516 KB Output is correct
4 Correct 1471 ms 626372 KB Output is correct
5 Correct 1807 ms 647068 KB Output is correct
6 Correct 2097 ms 671040 KB Output is correct
7 Correct 2609 ms 701764 KB Output is correct
8 Correct 2495 ms 701804 KB Output is correct
9 Correct 2435 ms 701808 KB Output is correct
10 Correct 210 ms 493388 KB Output is correct
11 Correct 210 ms 493380 KB Output is correct
12 Correct 214 ms 493528 KB Output is correct
13 Correct 209 ms 493448 KB Output is correct
14 Correct 210 ms 493516 KB Output is correct
15 Correct 212 ms 493632 KB Output is correct
16 Correct 214 ms 493564 KB Output is correct
17 Correct 212 ms 493484 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 493428 KB Output is correct
2 Correct 205 ms 493388 KB Output is correct
3 Correct 213 ms 493528 KB Output is correct
4 Correct 204 ms 493484 KB Output is correct
5 Correct 213 ms 493432 KB Output is correct
6 Correct 221 ms 493376 KB Output is correct
7 Correct 233 ms 493488 KB Output is correct
8 Correct 210 ms 493488 KB Output is correct
9 Correct 212 ms 493384 KB Output is correct
10 Correct 207 ms 493492 KB Output is correct
11 Correct 210 ms 493636 KB Output is correct
12 Correct 240 ms 493460 KB Output is correct
13 Correct 210 ms 493580 KB Output is correct
14 Correct 210 ms 493528 KB Output is correct
15 Correct 213 ms 493492 KB Output is correct
16 Correct 209 ms 493452 KB Output is correct
17 Correct 209 ms 493492 KB Output is correct
18 Correct 221 ms 493396 KB Output is correct
19 Correct 207 ms 493544 KB Output is correct
20 Correct 211 ms 493468 KB Output is correct
21 Correct 209 ms 493608 KB Output is correct
22 Correct 216 ms 493636 KB Output is correct
23 Correct 209 ms 493644 KB Output is correct
24 Correct 215 ms 493732 KB Output is correct
25 Correct 233 ms 493664 KB Output is correct
26 Correct 211 ms 493608 KB Output is correct
27 Correct 215 ms 493648 KB Output is correct
28 Correct 211 ms 493632 KB Output is correct
29 Correct 209 ms 493644 KB Output is correct
30 Correct 214 ms 493628 KB Output is correct
31 Correct 209 ms 493600 KB Output is correct
32 Correct 231 ms 493644 KB Output is correct
33 Correct 211 ms 493676 KB Output is correct
34 Correct 208 ms 493356 KB Output is correct
35 Correct 210 ms 493440 KB Output is correct
36 Correct 211 ms 493516 KB Output is correct
37 Correct 209 ms 493412 KB Output is correct
38 Correct 210 ms 493544 KB Output is correct
39 Correct 213 ms 493652 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 493428 KB Output is correct
2 Correct 205 ms 493388 KB Output is correct
3 Correct 213 ms 493528 KB Output is correct
4 Correct 204 ms 493484 KB Output is correct
5 Correct 213 ms 493432 KB Output is correct
6 Correct 221 ms 493376 KB Output is correct
7 Correct 233 ms 493488 KB Output is correct
8 Correct 210 ms 493488 KB Output is correct
9 Correct 212 ms 493384 KB Output is correct
10 Correct 207 ms 493492 KB Output is correct
11 Correct 210 ms 493636 KB Output is correct
12 Correct 240 ms 493460 KB Output is correct
13 Correct 210 ms 493580 KB Output is correct
14 Correct 210 ms 493528 KB Output is correct
15 Correct 213 ms 493492 KB Output is correct
16 Correct 209 ms 493452 KB Output is correct
17 Correct 209 ms 493492 KB Output is correct
18 Correct 221 ms 493396 KB Output is correct
19 Correct 207 ms 493544 KB Output is correct
20 Correct 211 ms 493468 KB Output is correct
21 Correct 209 ms 493608 KB Output is correct
22 Correct 216 ms 493636 KB Output is correct
23 Correct 209 ms 493644 KB Output is correct
24 Correct 215 ms 493732 KB Output is correct
25 Correct 233 ms 493664 KB Output is correct
26 Correct 211 ms 493608 KB Output is correct
27 Correct 215 ms 493648 KB Output is correct
28 Correct 211 ms 493632 KB Output is correct
29 Correct 209 ms 493644 KB Output is correct
30 Correct 214 ms 493628 KB Output is correct
31 Correct 209 ms 493600 KB Output is correct
32 Correct 231 ms 493644 KB Output is correct
33 Correct 211 ms 493676 KB Output is correct
34 Correct 208 ms 493356 KB Output is correct
35 Correct 210 ms 493440 KB Output is correct
36 Correct 211 ms 493516 KB Output is correct
37 Correct 209 ms 493412 KB Output is correct
38 Correct 210 ms 493544 KB Output is correct
39 Correct 213 ms 493652 KB Output is correct
40 Correct 212 ms 494540 KB Output is correct
41 Correct 215 ms 495596 KB Output is correct
42 Correct 240 ms 499104 KB Output is correct
43 Correct 228 ms 498960 KB Output is correct
44 Correct 227 ms 499028 KB Output is correct
45 Correct 228 ms 499100 KB Output is correct
46 Correct 224 ms 499096 KB Output is correct
47 Correct 216 ms 496076 KB Output is correct
48 Correct 226 ms 497552 KB Output is correct
49 Correct 219 ms 498076 KB Output is correct
50 Correct 219 ms 498200 KB Output is correct
51 Correct 225 ms 497432 KB Output is correct
52 Correct 216 ms 497348 KB Output is correct
53 Correct 221 ms 499144 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 493428 KB Output is correct
2 Correct 205 ms 493388 KB Output is correct
3 Correct 213 ms 493528 KB Output is correct
4 Correct 204 ms 493484 KB Output is correct
5 Correct 213 ms 493432 KB Output is correct
6 Correct 221 ms 493376 KB Output is correct
7 Correct 233 ms 493488 KB Output is correct
8 Correct 210 ms 493488 KB Output is correct
9 Correct 212 ms 493384 KB Output is correct
10 Correct 207 ms 493492 KB Output is correct
11 Correct 210 ms 493636 KB Output is correct
12 Correct 240 ms 493460 KB Output is correct
13 Correct 210 ms 493580 KB Output is correct
14 Correct 210 ms 493528 KB Output is correct
15 Correct 213 ms 493492 KB Output is correct
16 Correct 209 ms 493452 KB Output is correct
17 Correct 209 ms 493492 KB Output is correct
18 Correct 221 ms 493396 KB Output is correct
19 Correct 207 ms 493544 KB Output is correct
20 Correct 211 ms 493468 KB Output is correct
21 Correct 209 ms 493608 KB Output is correct
22 Correct 216 ms 493636 KB Output is correct
23 Correct 209 ms 493644 KB Output is correct
24 Correct 215 ms 493732 KB Output is correct
25 Correct 233 ms 493664 KB Output is correct
26 Correct 211 ms 493608 KB Output is correct
27 Correct 215 ms 493648 KB Output is correct
28 Correct 211 ms 493632 KB Output is correct
29 Correct 209 ms 493644 KB Output is correct
30 Correct 214 ms 493628 KB Output is correct
31 Correct 209 ms 493600 KB Output is correct
32 Correct 231 ms 493644 KB Output is correct
33 Correct 211 ms 493676 KB Output is correct
34 Correct 208 ms 493356 KB Output is correct
35 Correct 210 ms 493440 KB Output is correct
36 Correct 211 ms 493516 KB Output is correct
37 Correct 209 ms 493412 KB Output is correct
38 Correct 210 ms 493544 KB Output is correct
39 Correct 213 ms 493652 KB Output is correct
40 Correct 212 ms 494540 KB Output is correct
41 Correct 215 ms 495596 KB Output is correct
42 Correct 240 ms 499104 KB Output is correct
43 Correct 228 ms 498960 KB Output is correct
44 Correct 227 ms 499028 KB Output is correct
45 Correct 228 ms 499100 KB Output is correct
46 Correct 224 ms 499096 KB Output is correct
47 Correct 216 ms 496076 KB Output is correct
48 Correct 226 ms 497552 KB Output is correct
49 Correct 219 ms 498076 KB Output is correct
50 Correct 219 ms 498200 KB Output is correct
51 Correct 225 ms 497432 KB Output is correct
52 Correct 216 ms 497348 KB Output is correct
53 Correct 221 ms 499144 KB Output is correct
54 Correct 300 ms 519484 KB Output is correct
55 Correct 436 ms 529308 KB Output is correct
56 Correct 762 ms 618960 KB Output is correct
57 Correct 744 ms 619628 KB Output is correct
58 Correct 738 ms 620004 KB Output is correct
59 Correct 745 ms 620272 KB Output is correct
60 Correct 741 ms 620332 KB Output is correct
61 Correct 502 ms 563632 KB Output is correct
62 Correct 404 ms 530300 KB Output is correct
63 Correct 649 ms 596720 KB Output is correct
64 Correct 643 ms 597616 KB Output is correct
65 Correct 564 ms 570388 KB Output is correct
66 Correct 568 ms 570464 KB Output is correct
67 Correct 747 ms 620344 KB Output is correct

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 493428 KB Output is correct
2 Correct 205 ms 493388 KB Output is correct
3 Correct 213 ms 493528 KB Output is correct
4 Correct 204 ms 493484 KB Output is correct
5 Correct 213 ms 493432 KB Output is correct
6 Correct 221 ms 493376 KB Output is correct
7 Correct 233 ms 493488 KB Output is correct
8 Correct 210 ms 493488 KB Output is correct
9 Correct 212 ms 493384 KB Output is correct
10 Correct 207 ms 493492 KB Output is correct
11 Correct 220 ms 493476 KB Output is correct
12 Correct 210 ms 493420 KB Output is correct
13 Correct 1380 ms 608516 KB Output is correct
14 Correct 1471 ms 626372 KB Output is correct
15 Correct 1807 ms 647068 KB Output is correct
16 Correct 2097 ms 671040 KB Output is correct
17 Correct 2609 ms 701764 KB Output is correct
18 Correct 2495 ms 701804 KB Output is correct
19 Correct 2435 ms 701808 KB Output is correct
20 Correct 210 ms 493388 KB Output is correct
21 Correct 210 ms 493380 KB Output is correct
22 Correct 214 ms 493528 KB Output is correct
23 Correct 209 ms 493448 KB Output is correct
24 Correct 210 ms 493516 KB Output is correct
25 Correct 212 ms 493632 KB Output is correct
26 Correct 214 ms 493564 KB Output is correct
27 Correct 212 ms 493484 KB Output is correct
28 Correct 210 ms 493636 KB Output is correct
29 Correct 240 ms 493460 KB Output is correct
30 Correct 210 ms 493580 KB Output is correct
31 Correct 210 ms 493528 KB Output is correct
32 Correct 213 ms 493492 KB Output is correct
33 Correct 209 ms 493452 KB Output is correct
34 Correct 209 ms 493492 KB Output is correct
35 Correct 221 ms 493396 KB Output is correct
36 Correct 207 ms 493544 KB Output is correct
37 Correct 211 ms 493468 KB Output is correct
38 Correct 209 ms 493608 KB Output is correct
39 Correct 216 ms 493636 KB Output is correct
40 Correct 209 ms 493644 KB Output is correct
41 Correct 215 ms 493732 KB Output is correct
42 Correct 233 ms 493664 KB Output is correct
43 Correct 211 ms 493608 KB Output is correct
44 Correct 215 ms 493648 KB Output is correct
45 Correct 211 ms 493632 KB Output is correct
46 Correct 209 ms 493644 KB Output is correct
47 Correct 214 ms 493628 KB Output is correct
48 Correct 209 ms 493600 KB Output is correct
49 Correct 231 ms 493644 KB Output is correct
50 Correct 211 ms 493676 KB Output is correct
51 Correct 208 ms 493356 KB Output is correct
52 Correct 210 ms 493440 KB Output is correct
53 Correct 211 ms 493516 KB Output is correct
54 Correct 209 ms 493412 KB Output is correct
55 Correct 210 ms 493544 KB Output is correct
56 Correct 213 ms 493652 KB Output is correct
57 Correct 212 ms 494540 KB Output is correct
58 Correct 215 ms 495596 KB Output is correct
59 Correct 240 ms 499104 KB Output is correct
60 Correct 228 ms 498960 KB Output is correct
61 Correct 227 ms 499028 KB Output is correct
62 Correct 228 ms 499100 KB Output is correct
63 Correct 224 ms 499096 KB Output is correct
64 Correct 216 ms 496076 KB Output is correct
65 Correct 226 ms 497552 KB Output is correct
66 Correct 219 ms 498076 KB Output is correct
67 Correct 219 ms 498200 KB Output is correct
68 Correct 225 ms 497432 KB Output is correct
69 Correct 216 ms 497348 KB Output is correct
70 Correct 221 ms 499144 KB Output is correct
71 Correct 300 ms 519484 KB Output is correct
72 Correct 436 ms 529308 KB Output is correct
73 Correct 762 ms 618960 KB Output is correct
74 Correct 744 ms 619628 KB Output is correct
75 Correct 738 ms 620004 KB Output is correct
76 Correct 745 ms 620272 KB Output is correct
77 Correct 741 ms 620332 KB Output is correct
78 Correct 502 ms 563632 KB Output is correct
79 Correct 404 ms 530300 KB Output is correct
80 Correct 649 ms 596720 KB Output is correct
81 Correct 643 ms 597616 KB Output is correct
82 Correct 564 ms 570388 KB Output is correct
83 Correct 568 ms 570464 KB Output is correct
84 Correct 747 ms 620344 KB Output is correct
85 Correct 1969 ms 802184 KB Output is correct
86 Execution timed out 3104 ms 894180 KB Time limit exceeded
87 Halted 0 ms 0 KB -