oj.uz

Submission #776776

# Submission time Handle Problem Language Result Execution time Memory
776776 2023-07-08T08:58:25 Z danikoynov Copy and Paste 3 (JOI22_copypaste3) C++14
62 / 100
 3000 ms 1259772 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 (i == 0 || cp[i] != cp[i - 1])
        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 234 ms 493484 KB Output is correct
2 Correct 204 ms 493456 KB Output is correct
3 Correct 208 ms 493400 KB Output is correct
4 Correct 208 ms 493604 KB Output is correct
5 Correct 226 ms 493476 KB Output is correct
6 Correct 208 ms 493484 KB Output is correct
7 Correct 209 ms 493480 KB Output is correct
8 Correct 205 ms 493428 KB Output is correct
9 Correct 205 ms 493480 KB Output is correct
10 Correct 205 ms 493372 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 493488 KB Output is correct
2 Correct 203 ms 493404 KB Output is correct
3 Correct 1198 ms 621064 KB Output is correct
4 Correct 1466 ms 640116 KB Output is correct
5 Correct 1711 ms 662268 KB Output is correct
6 Correct 2004 ms 687548 KB Output is correct
7 Correct 2444 ms 719724 KB Output is correct
8 Correct 2454 ms 719824 KB Output is correct
9 Correct 2580 ms 719792 KB Output is correct
10 Correct 209 ms 493356 KB Output is correct
11 Correct 204 ms 493444 KB Output is correct
12 Correct 209 ms 493612 KB Output is correct
13 Correct 206 ms 493460 KB Output is correct
14 Correct 205 ms 493516 KB Output is correct
15 Correct 205 ms 493544 KB Output is correct
16 Correct 203 ms 493520 KB Output is correct
17 Correct 214 ms 493428 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 493484 KB Output is correct
2 Correct 204 ms 493456 KB Output is correct
3 Correct 208 ms 493400 KB Output is correct
4 Correct 208 ms 493604 KB Output is correct
5 Correct 226 ms 493476 KB Output is correct
6 Correct 208 ms 493484 KB Output is correct
7 Correct 209 ms 493480 KB Output is correct
8 Correct 205 ms 493428 KB Output is correct
9 Correct 205 ms 493480 KB Output is correct
10 Correct 205 ms 493372 KB Output is correct
11 Correct 208 ms 493420 KB Output is correct
12 Correct 210 ms 493548 KB Output is correct
13 Correct 205 ms 493464 KB Output is correct
14 Correct 208 ms 493528 KB Output is correct
15 Correct 209 ms 493628 KB Output is correct
16 Correct 204 ms 493536 KB Output is correct
17 Correct 203 ms 493452 KB Output is correct
18 Correct 208 ms 493476 KB Output is correct
19 Correct 205 ms 493516 KB Output is correct
20 Correct 206 ms 493472 KB Output is correct
21 Correct 210 ms 493644 KB Output is correct
22 Correct 210 ms 493696 KB Output is correct
23 Correct 208 ms 493644 KB Output is correct
24 Correct 209 ms 493744 KB Output is correct
25 Correct 215 ms 493644 KB Output is correct
26 Correct 221 ms 493632 KB Output is correct
27 Correct 213 ms 493700 KB Output is correct
28 Correct 203 ms 493576 KB Output is correct
29 Correct 240 ms 493692 KB Output is correct
30 Correct 210 ms 493780 KB Output is correct
31 Correct 206 ms 493600 KB Output is correct
32 Correct 205 ms 493656 KB Output is correct
33 Correct 201 ms 493716 KB Output is correct
34 Correct 210 ms 493480 KB Output is correct
35 Correct 227 ms 493480 KB Output is correct
36 Correct 207 ms 493460 KB Output is correct
37 Correct 212 ms 493424 KB Output is correct
38 Correct 204 ms 493524 KB Output is correct
39 Correct 215 ms 493516 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 493484 KB Output is correct
2 Correct 204 ms 493456 KB Output is correct
3 Correct 208 ms 493400 KB Output is correct
4 Correct 208 ms 493604 KB Output is correct
5 Correct 226 ms 493476 KB Output is correct
6 Correct 208 ms 493484 KB Output is correct
7 Correct 209 ms 493480 KB Output is correct
8 Correct 205 ms 493428 KB Output is correct
9 Correct 205 ms 493480 KB Output is correct
10 Correct 205 ms 493372 KB Output is correct
11 Correct 208 ms 493420 KB Output is correct
12 Correct 210 ms 493548 KB Output is correct
13 Correct 205 ms 493464 KB Output is correct
14 Correct 208 ms 493528 KB Output is correct
15 Correct 209 ms 493628 KB Output is correct
16 Correct 204 ms 493536 KB Output is correct
17 Correct 203 ms 493452 KB Output is correct
18 Correct 208 ms 493476 KB Output is correct
19 Correct 205 ms 493516 KB Output is correct
20 Correct 206 ms 493472 KB Output is correct
21 Correct 210 ms 493644 KB Output is correct
22 Correct 210 ms 493696 KB Output is correct
23 Correct 208 ms 493644 KB Output is correct
24 Correct 209 ms 493744 KB Output is correct
25 Correct 215 ms 493644 KB Output is correct
26 Correct 221 ms 493632 KB Output is correct
27 Correct 213 ms 493700 KB Output is correct
28 Correct 203 ms 493576 KB Output is correct
29 Correct 240 ms 493692 KB Output is correct
30 Correct 210 ms 493780 KB Output is correct
31 Correct 206 ms 493600 KB Output is correct
32 Correct 205 ms 493656 KB Output is correct
33 Correct 201 ms 493716 KB Output is correct
34 Correct 210 ms 493480 KB Output is correct
35 Correct 227 ms 493480 KB Output is correct
36 Correct 207 ms 493460 KB Output is correct
37 Correct 212 ms 493424 KB Output is correct
38 Correct 204 ms 493524 KB Output is correct
39 Correct 215 ms 493516 KB Output is correct
40 Correct 214 ms 494664 KB Output is correct
41 Correct 222 ms 495884 KB Output is correct
42 Correct 217 ms 498908 KB Output is correct
43 Correct 232 ms 499016 KB Output is correct
44 Correct 212 ms 499012 KB Output is correct
45 Correct 242 ms 499092 KB Output is correct
46 Correct 215 ms 499096 KB Output is correct
47 Correct 212 ms 496412 KB Output is correct
48 Correct 244 ms 497640 KB Output is correct
49 Correct 215 ms 498116 KB Output is correct
50 Correct 224 ms 498280 KB Output is correct
51 Correct 215 ms 497548 KB Output is correct
52 Correct 229 ms 497480 KB Output is correct
53 Correct 232 ms 499144 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 493484 KB Output is correct
2 Correct 204 ms 493456 KB Output is correct
3 Correct 208 ms 493400 KB Output is correct
4 Correct 208 ms 493604 KB Output is correct
5 Correct 226 ms 493476 KB Output is correct
6 Correct 208 ms 493484 KB Output is correct
7 Correct 209 ms 493480 KB Output is correct
8 Correct 205 ms 493428 KB Output is correct
9 Correct 205 ms 493480 KB Output is correct
10 Correct 205 ms 493372 KB Output is correct
11 Correct 208 ms 493420 KB Output is correct
12 Correct 210 ms 493548 KB Output is correct
13 Correct 205 ms 493464 KB Output is correct
14 Correct 208 ms 493528 KB Output is correct
15 Correct 209 ms 493628 KB Output is correct
16 Correct 204 ms 493536 KB Output is correct
17 Correct 203 ms 493452 KB Output is correct
18 Correct 208 ms 493476 KB Output is correct
19 Correct 205 ms 493516 KB Output is correct
20 Correct 206 ms 493472 KB Output is correct
21 Correct 210 ms 493644 KB Output is correct
22 Correct 210 ms 493696 KB Output is correct
23 Correct 208 ms 493644 KB Output is correct
24 Correct 209 ms 493744 KB Output is correct
25 Correct 215 ms 493644 KB Output is correct
26 Correct 221 ms 493632 KB Output is correct
27 Correct 213 ms 493700 KB Output is correct
28 Correct 203 ms 493576 KB Output is correct
29 Correct 240 ms 493692 KB Output is correct
30 Correct 210 ms 493780 KB Output is correct
31 Correct 206 ms 493600 KB Output is correct
32 Correct 205 ms 493656 KB Output is correct
33 Correct 201 ms 493716 KB Output is correct
34 Correct 210 ms 493480 KB Output is correct
35 Correct 227 ms 493480 KB Output is correct
36 Correct 207 ms 493460 KB Output is correct
37 Correct 212 ms 493424 KB Output is correct
38 Correct 204 ms 493524 KB Output is correct
39 Correct 215 ms 493516 KB Output is correct
40 Correct 214 ms 494664 KB Output is correct
41 Correct 222 ms 495884 KB Output is correct
42 Correct 217 ms 498908 KB Output is correct
43 Correct 232 ms 499016 KB Output is correct
44 Correct 212 ms 499012 KB Output is correct
45 Correct 242 ms 499092 KB Output is correct
46 Correct 215 ms 499096 KB Output is correct
47 Correct 212 ms 496412 KB Output is correct
48 Correct 244 ms 497640 KB Output is correct
49 Correct 215 ms 498116 KB Output is correct
50 Correct 224 ms 498280 KB Output is correct
51 Correct 215 ms 497548 KB Output is correct
52 Correct 229 ms 497480 KB Output is correct
53 Correct 232 ms 499144 KB Output is correct
54 Correct 251 ms 519608 KB Output is correct
55 Correct 445 ms 535192 KB Output is correct
56 Correct 480 ms 619140 KB Output is correct
57 Correct 479 ms 619648 KB Output is correct
58 Correct 462 ms 620144 KB Output is correct
59 Correct 498 ms 620220 KB Output is correct
60 Correct 507 ms 620364 KB Output is correct
61 Correct 337 ms 567728 KB Output is correct
62 Correct 377 ms 536132 KB Output is correct
63 Correct 389 ms 598688 KB Output is correct
64 Correct 412 ms 599628 KB Output is correct
65 Correct 359 ms 574424 KB Output is correct
66 Correct 365 ms 574480 KB Output is correct
67 Correct 418 ms 620288 KB Output is correct

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 493484 KB Output is correct
2 Correct 204 ms 493456 KB Output is correct
3 Correct 208 ms 493400 KB Output is correct
4 Correct 208 ms 493604 KB Output is correct
5 Correct 226 ms 493476 KB Output is correct
6 Correct 208 ms 493484 KB Output is correct
7 Correct 209 ms 493480 KB Output is correct
8 Correct 205 ms 493428 KB Output is correct
9 Correct 205 ms 493480 KB Output is correct
10 Correct 205 ms 493372 KB Output is correct
11 Correct 212 ms 493488 KB Output is correct
12 Correct 203 ms 493404 KB Output is correct
13 Correct 1198 ms 621064 KB Output is correct
14 Correct 1466 ms 640116 KB Output is correct
15 Correct 1711 ms 662268 KB Output is correct
16 Correct 2004 ms 687548 KB Output is correct
17 Correct 2444 ms 719724 KB Output is correct
18 Correct 2454 ms 719824 KB Output is correct
19 Correct 2580 ms 719792 KB Output is correct
20 Correct 209 ms 493356 KB Output is correct
21 Correct 204 ms 493444 KB Output is correct
22 Correct 209 ms 493612 KB Output is correct
23 Correct 206 ms 493460 KB Output is correct
24 Correct 205 ms 493516 KB Output is correct
25 Correct 205 ms 493544 KB Output is correct
26 Correct 203 ms 493520 KB Output is correct
27 Correct 214 ms 493428 KB Output is correct
28 Correct 208 ms 493420 KB Output is correct
29 Correct 210 ms 493548 KB Output is correct
30 Correct 205 ms 493464 KB Output is correct
31 Correct 208 ms 493528 KB Output is correct
32 Correct 209 ms 493628 KB Output is correct
33 Correct 204 ms 493536 KB Output is correct
34 Correct 203 ms 493452 KB Output is correct
35 Correct 208 ms 493476 KB Output is correct
36 Correct 205 ms 493516 KB Output is correct
37 Correct 206 ms 493472 KB Output is correct
38 Correct 210 ms 493644 KB Output is correct
39 Correct 210 ms 493696 KB Output is correct
40 Correct 208 ms 493644 KB Output is correct
41 Correct 209 ms 493744 KB Output is correct
42 Correct 215 ms 493644 KB Output is correct
43 Correct 221 ms 493632 KB Output is correct
44 Correct 213 ms 493700 KB Output is correct
45 Correct 203 ms 493576 KB Output is correct
46 Correct 240 ms 493692 KB Output is correct
47 Correct 210 ms 493780 KB Output is correct
48 Correct 206 ms 493600 KB Output is correct
49 Correct 205 ms 493656 KB Output is correct
50 Correct 201 ms 493716 KB Output is correct
51 Correct 210 ms 493480 KB Output is correct
52 Correct 227 ms 493480 KB Output is correct
53 Correct 207 ms 493460 KB Output is correct
54 Correct 212 ms 493424 KB Output is correct
55 Correct 204 ms 493524 KB Output is correct
56 Correct 215 ms 493516 KB Output is correct
57 Correct 214 ms 494664 KB Output is correct
58 Correct 222 ms 495884 KB Output is correct
59 Correct 217 ms 498908 KB Output is correct
60 Correct 232 ms 499016 KB Output is correct
61 Correct 212 ms 499012 KB Output is correct
62 Correct 242 ms 499092 KB Output is correct
63 Correct 215 ms 499096 KB Output is correct
64 Correct 212 ms 496412 KB Output is correct
65 Correct 244 ms 497640 KB Output is correct
66 Correct 215 ms 498116 KB Output is correct
67 Correct 224 ms 498280 KB Output is correct
68 Correct 215 ms 497548 KB Output is correct
69 Correct 229 ms 497480 KB Output is correct
70 Correct 232 ms 499144 KB Output is correct
71 Correct 251 ms 519608 KB Output is correct
72 Correct 445 ms 535192 KB Output is correct
73 Correct 480 ms 619140 KB Output is correct
74 Correct 479 ms 619648 KB Output is correct
75 Correct 462 ms 620144 KB Output is correct
76 Correct 498 ms 620220 KB Output is correct
77 Correct 507 ms 620364 KB Output is correct
78 Correct 337 ms 567728 KB Output is correct
79 Correct 377 ms 536132 KB Output is correct
80 Correct 389 ms 598688 KB Output is correct
81 Correct 412 ms 599628 KB Output is correct
82 Correct 359 ms 574424 KB Output is correct
83 Correct 365 ms 574480 KB Output is correct
84 Correct 418 ms 620288 KB Output is correct
85 Correct 978 ms 802372 KB Output is correct
86 Execution timed out 3134 ms 1259772 KB Time limit exceeded
87 Halted 0 ms 0 KB -