oj.uz

Submission #776778

# Submission time Handle Problem Language Result Execution time Memory
776778 2023-07-08T08:59:25 Z danikoynov Copy and Paste 3 (JOI22_copypaste3) C++14
62 / 100
 3000 ms 1279412 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]);
        }
    ///cp.erase(unique(cp.begin(), cp.end()), cp.end());
    ///sort(cp.begin(), cp.end());
    int cnt = 0;
    for (int i = 0; i < cp.size(); i ++)
    {
        if (rev[cp[i]] == 0)
        rev[cp[i]] = i + 1;
    }

    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 ++)
        {
            int 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[range_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[range_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 ++)
        {
            int 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[range_hash[i][pos]] = min(hs_dp[range_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[range_hash[i][k]] = min(hs_dp[range_hash[i][k]], hs_dp[range_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[range_hash[1][n]] << endl;


}

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

Compilation message

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

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 493368 KB Output is correct
2 Correct 253 ms 493452 KB Output is correct
3 Correct 259 ms 493480 KB Output is correct
4 Correct 254 ms 493372 KB Output is correct
5 Correct 256 ms 493400 KB Output is correct
6 Correct 252 ms 493388 KB Output is correct
7 Correct 249 ms 493392 KB Output is correct
8 Correct 252 ms 493488 KB Output is correct
9 Correct 253 ms 493420 KB Output is correct
10 Correct 251 ms 493364 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 493516 KB Output is correct
2 Correct 249 ms 493492 KB Output is correct
3 Correct 1131 ms 608496 KB Output is correct
4 Correct 1311 ms 626396 KB Output is correct
5 Correct 1582 ms 647228 KB Output is correct
6 Correct 1919 ms 670996 KB Output is correct
7 Correct 2258 ms 701832 KB Output is correct
8 Correct 2199 ms 701744 KB Output is correct
9 Correct 2294 ms 701808 KB Output is correct
10 Correct 254 ms 493408 KB Output is correct
11 Correct 258 ms 493408 KB Output is correct
12 Correct 251 ms 493488 KB Output is correct
13 Correct 350 ms 493560 KB Output is correct
14 Correct 252 ms 493656 KB Output is correct
15 Correct 264 ms 493540 KB Output is correct
16 Correct 295 ms 493516 KB Output is correct
17 Correct 274 ms 493404 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 493368 KB Output is correct
2 Correct 253 ms 493452 KB Output is correct
3 Correct 259 ms 493480 KB Output is correct
4 Correct 254 ms 493372 KB Output is correct
5 Correct 256 ms 493400 KB Output is correct
6 Correct 252 ms 493388 KB Output is correct
7 Correct 249 ms 493392 KB Output is correct
8 Correct 252 ms 493488 KB Output is correct
9 Correct 253 ms 493420 KB Output is correct
10 Correct 251 ms 493364 KB Output is correct
11 Correct 252 ms 493496 KB Output is correct
12 Correct 252 ms 493528 KB Output is correct
13 Correct 251 ms 493528 KB Output is correct
14 Correct 265 ms 493452 KB Output is correct
15 Correct 274 ms 493644 KB Output is correct
16 Correct 258 ms 493476 KB Output is correct
17 Correct 268 ms 493388 KB Output is correct
18 Correct 251 ms 493448 KB Output is correct
19 Correct 250 ms 493516 KB Output is correct
20 Correct 254 ms 493476 KB Output is correct
21 Correct 255 ms 493740 KB Output is correct
22 Correct 253 ms 493648 KB Output is correct
23 Correct 253 ms 493648 KB Output is correct
24 Correct 253 ms 493616 KB Output is correct
25 Correct 266 ms 493644 KB Output is correct
26 Correct 253 ms 493844 KB Output is correct
27 Correct 249 ms 493620 KB Output is correct
28 Correct 252 ms 493644 KB Output is correct
29 Correct 253 ms 493708 KB Output is correct
30 Correct 253 ms 493696 KB Output is correct
31 Correct 283 ms 493692 KB Output is correct
32 Correct 255 ms 493680 KB Output is correct
33 Correct 252 ms 493604 KB Output is correct
34 Correct 254 ms 493388 KB Output is correct
35 Correct 253 ms 493372 KB Output is correct
36 Correct 251 ms 493476 KB Output is correct
37 Correct 253 ms 493516 KB Output is correct
38 Correct 256 ms 493496 KB Output is correct
39 Correct 260 ms 493516 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 493368 KB Output is correct
2 Correct 253 ms 493452 KB Output is correct
3 Correct 259 ms 493480 KB Output is correct
4 Correct 254 ms 493372 KB Output is correct
5 Correct 256 ms 493400 KB Output is correct
6 Correct 252 ms 493388 KB Output is correct
7 Correct 249 ms 493392 KB Output is correct
8 Correct 252 ms 493488 KB Output is correct
9 Correct 253 ms 493420 KB Output is correct
10 Correct 251 ms 493364 KB Output is correct
11 Correct 252 ms 493496 KB Output is correct
12 Correct 252 ms 493528 KB Output is correct
13 Correct 251 ms 493528 KB Output is correct
14 Correct 265 ms 493452 KB Output is correct
15 Correct 274 ms 493644 KB Output is correct
16 Correct 258 ms 493476 KB Output is correct
17 Correct 268 ms 493388 KB Output is correct
18 Correct 251 ms 493448 KB Output is correct
19 Correct 250 ms 493516 KB Output is correct
20 Correct 254 ms 493476 KB Output is correct
21 Correct 255 ms 493740 KB Output is correct
22 Correct 253 ms 493648 KB Output is correct
23 Correct 253 ms 493648 KB Output is correct
24 Correct 253 ms 493616 KB Output is correct
25 Correct 266 ms 493644 KB Output is correct
26 Correct 253 ms 493844 KB Output is correct
27 Correct 249 ms 493620 KB Output is correct
28 Correct 252 ms 493644 KB Output is correct
29 Correct 253 ms 493708 KB Output is correct
30 Correct 253 ms 493696 KB Output is correct
31 Correct 283 ms 493692 KB Output is correct
32 Correct 255 ms 493680 KB Output is correct
33 Correct 252 ms 493604 KB Output is correct
34 Correct 254 ms 493388 KB Output is correct
35 Correct 253 ms 493372 KB Output is correct
36 Correct 251 ms 493476 KB Output is correct
37 Correct 253 ms 493516 KB Output is correct
38 Correct 256 ms 493496 KB Output is correct
39 Correct 260 ms 493516 KB Output is correct
40 Correct 257 ms 494640 KB Output is correct
41 Correct 257 ms 495580 KB Output is correct
42 Correct 262 ms 498888 KB Output is correct
43 Correct 262 ms 498976 KB Output is correct
44 Correct 263 ms 499016 KB Output is correct
45 Correct 269 ms 499060 KB Output is correct
46 Correct 265 ms 499036 KB Output is correct
47 Correct 259 ms 496168 KB Output is correct
48 Correct 268 ms 497580 KB Output is correct
49 Correct 257 ms 498140 KB Output is correct
50 Correct 256 ms 498252 KB Output is correct
51 Correct 263 ms 497440 KB Output is correct
52 Correct 263 ms 497368 KB Output is correct
53 Correct 261 ms 499104 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 493368 KB Output is correct
2 Correct 253 ms 493452 KB Output is correct
3 Correct 259 ms 493480 KB Output is correct
4 Correct 254 ms 493372 KB Output is correct
5 Correct 256 ms 493400 KB Output is correct
6 Correct 252 ms 493388 KB Output is correct
7 Correct 249 ms 493392 KB Output is correct
8 Correct 252 ms 493488 KB Output is correct
9 Correct 253 ms 493420 KB Output is correct
10 Correct 251 ms 493364 KB Output is correct
11 Correct 252 ms 493496 KB Output is correct
12 Correct 252 ms 493528 KB Output is correct
13 Correct 251 ms 493528 KB Output is correct
14 Correct 265 ms 493452 KB Output is correct
15 Correct 274 ms 493644 KB Output is correct
16 Correct 258 ms 493476 KB Output is correct
17 Correct 268 ms 493388 KB Output is correct
18 Correct 251 ms 493448 KB Output is correct
19 Correct 250 ms 493516 KB Output is correct
20 Correct 254 ms 493476 KB Output is correct
21 Correct 255 ms 493740 KB Output is correct
22 Correct 253 ms 493648 KB Output is correct
23 Correct 253 ms 493648 KB Output is correct
24 Correct 253 ms 493616 KB Output is correct
25 Correct 266 ms 493644 KB Output is correct
26 Correct 253 ms 493844 KB Output is correct
27 Correct 249 ms 493620 KB Output is correct
28 Correct 252 ms 493644 KB Output is correct
29 Correct 253 ms 493708 KB Output is correct
30 Correct 253 ms 493696 KB Output is correct
31 Correct 283 ms 493692 KB Output is correct
32 Correct 255 ms 493680 KB Output is correct
33 Correct 252 ms 493604 KB Output is correct
34 Correct 254 ms 493388 KB Output is correct
35 Correct 253 ms 493372 KB Output is correct
36 Correct 251 ms 493476 KB Output is correct
37 Correct 253 ms 493516 KB Output is correct
38 Correct 256 ms 493496 KB Output is correct
39 Correct 260 ms 493516 KB Output is correct
40 Correct 257 ms 494640 KB Output is correct
41 Correct 257 ms 495580 KB Output is correct
42 Correct 262 ms 498888 KB Output is correct
43 Correct 262 ms 498976 KB Output is correct
44 Correct 263 ms 499016 KB Output is correct
45 Correct 269 ms 499060 KB Output is correct
46 Correct 265 ms 499036 KB Output is correct
47 Correct 259 ms 496168 KB Output is correct
48 Correct 268 ms 497580 KB Output is correct
49 Correct 257 ms 498140 KB Output is correct
50 Correct 256 ms 498252 KB Output is correct
51 Correct 263 ms 497440 KB Output is correct
52 Correct 263 ms 497368 KB Output is correct
53 Correct 261 ms 499104 KB Output is correct
54 Correct 301 ms 519596 KB Output is correct
55 Correct 444 ms 529220 KB Output is correct
56 Correct 530 ms 619176 KB Output is correct
57 Correct 499 ms 619676 KB Output is correct
58 Correct 500 ms 620044 KB Output is correct
59 Correct 490 ms 620300 KB Output is correct
60 Correct 489 ms 620408 KB Output is correct
61 Correct 412 ms 563756 KB Output is correct
62 Correct 397 ms 530220 KB Output is correct
63 Correct 451 ms 598668 KB Output is correct
64 Correct 467 ms 599216 KB Output is correct
65 Correct 442 ms 573212 KB Output is correct
66 Correct 411 ms 573268 KB Output is correct
67 Correct 512 ms 620292 KB Output is correct

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 493368 KB Output is correct
2 Correct 253 ms 493452 KB Output is correct
3 Correct 259 ms 493480 KB Output is correct
4 Correct 254 ms 493372 KB Output is correct
5 Correct 256 ms 493400 KB Output is correct
6 Correct 252 ms 493388 KB Output is correct
7 Correct 249 ms 493392 KB Output is correct
8 Correct 252 ms 493488 KB Output is correct
9 Correct 253 ms 493420 KB Output is correct
10 Correct 251 ms 493364 KB Output is correct
11 Correct 250 ms 493516 KB Output is correct
12 Correct 249 ms 493492 KB Output is correct
13 Correct 1131 ms 608496 KB Output is correct
14 Correct 1311 ms 626396 KB Output is correct
15 Correct 1582 ms 647228 KB Output is correct
16 Correct 1919 ms 670996 KB Output is correct
17 Correct 2258 ms 701832 KB Output is correct
18 Correct 2199 ms 701744 KB Output is correct
19 Correct 2294 ms 701808 KB Output is correct
20 Correct 254 ms 493408 KB Output is correct
21 Correct 258 ms 493408 KB Output is correct
22 Correct 251 ms 493488 KB Output is correct
23 Correct 350 ms 493560 KB Output is correct
24 Correct 252 ms 493656 KB Output is correct
25 Correct 264 ms 493540 KB Output is correct
26 Correct 295 ms 493516 KB Output is correct
27 Correct 274 ms 493404 KB Output is correct
28 Correct 252 ms 493496 KB Output is correct
29 Correct 252 ms 493528 KB Output is correct
30 Correct 251 ms 493528 KB Output is correct
31 Correct 265 ms 493452 KB Output is correct
32 Correct 274 ms 493644 KB Output is correct
33 Correct 258 ms 493476 KB Output is correct
34 Correct 268 ms 493388 KB Output is correct
35 Correct 251 ms 493448 KB Output is correct
36 Correct 250 ms 493516 KB Output is correct
37 Correct 254 ms 493476 KB Output is correct
38 Correct 255 ms 493740 KB Output is correct
39 Correct 253 ms 493648 KB Output is correct
40 Correct 253 ms 493648 KB Output is correct
41 Correct 253 ms 493616 KB Output is correct
42 Correct 266 ms 493644 KB Output is correct
43 Correct 253 ms 493844 KB Output is correct
44 Correct 249 ms 493620 KB Output is correct
45 Correct 252 ms 493644 KB Output is correct
46 Correct 253 ms 493708 KB Output is correct
47 Correct 253 ms 493696 KB Output is correct
48 Correct 283 ms 493692 KB Output is correct
49 Correct 255 ms 493680 KB Output is correct
50 Correct 252 ms 493604 KB Output is correct
51 Correct 254 ms 493388 KB Output is correct
52 Correct 253 ms 493372 KB Output is correct
53 Correct 251 ms 493476 KB Output is correct
54 Correct 253 ms 493516 KB Output is correct
55 Correct 256 ms 493496 KB Output is correct
56 Correct 260 ms 493516 KB Output is correct
57 Correct 257 ms 494640 KB Output is correct
58 Correct 257 ms 495580 KB Output is correct
59 Correct 262 ms 498888 KB Output is correct
60 Correct 262 ms 498976 KB Output is correct
61 Correct 263 ms 499016 KB Output is correct
62 Correct 269 ms 499060 KB Output is correct
63 Correct 265 ms 499036 KB Output is correct
64 Correct 259 ms 496168 KB Output is correct
65 Correct 268 ms 497580 KB Output is correct
66 Correct 257 ms 498140 KB Output is correct
67 Correct 256 ms 498252 KB Output is correct
68 Correct 263 ms 497440 KB Output is correct
69 Correct 263 ms 497368 KB Output is correct
70 Correct 261 ms 499104 KB Output is correct
71 Correct 301 ms 519596 KB Output is correct
72 Correct 444 ms 529220 KB Output is correct
73 Correct 530 ms 619176 KB Output is correct
74 Correct 499 ms 619676 KB Output is correct
75 Correct 500 ms 620044 KB Output is correct
76 Correct 490 ms 620300 KB Output is correct
77 Correct 489 ms 620408 KB Output is correct
78 Correct 412 ms 563756 KB Output is correct
79 Correct 397 ms 530220 KB Output is correct
80 Correct 451 ms 598668 KB Output is correct
81 Correct 467 ms 599216 KB Output is correct
82 Correct 442 ms 573212 KB Output is correct
83 Correct 411 ms 573268 KB Output is correct
84 Correct 512 ms 620292 KB Output is correct
85 Correct 1084 ms 802404 KB Output is correct
86 Execution timed out 3134 ms 1279412 KB Time limit exceeded
87 Halted 0 ms 0 KB -