oj.uz

Submission #776735

# Submission time Handle Problem Language Result Execution time Memory
776735 2023-07-08T08:10:13 Z danikoynov Copy and Paste 3 (JOI22_copypaste3) C++14
25 / 100
 3000 ms 23336 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;
unordered_map < ll, vector < int > > occ;
unordered_map < ll, ll > hs_dp;
ll range_hash[maxn][maxn];
ll get_hash(int i, int j)
{
    return range_hash[i][j];
}


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;
    }
    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];


    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;
            }
            else
            {
                hs_dp[cur_hs] = min(hs_dp[cur_hs], hs_dp[get_hash(i + 1, p)] + a);
            }
        }


        for (int k = i; k <= n; k ++)
        {
            ll clip_hash, clip_len = k - i + 1;
            clip_hash = h[k] - h[i - 1] * pw[clip_len];
            ll cost = hs_dp[clip_hash] + b;
            if (occ[get_hash(i, k)].size() < 2)
                break;
            int pos = i, pt = (int)(occ[clip_hash].size()) - 1;
            ///cout << "-------------------" << endl;
            ///cout << i << " " << k << endl;
            while(pos <= n)
            {
                ///cout << pos << " " << cost << endl;
                while(pt >= 0 && occ[clip_hash][pt] < pos)
                    pt --;

                if (pt == -1)
                    break;
                ///cout << "stop " << occ[clip_hash][pt] << endl;
                cost = cost + (occ[clip_hash][pt] - pos) * a;
                cost = cost + c;
                pos = (occ[clip_hash][pt] + clip_len - 1);
                hs_dp[get_hash(i, pos)] = min(hs_dp[get_hash(i, pos)], cost);
                pos ++;

                /**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[h[n]] << endl;


}

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

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 308 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Execution timed out 3062 ms 23336 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 308 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 436 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 440 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Correct 1 ms 312 KB Output is correct
35 Correct 1 ms 312 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 340 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 2 ms 340 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 308 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 436 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 440 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Correct 1 ms 312 KB Output is correct
35 Correct 1 ms 312 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 340 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 2 ms 340 KB Output is correct
40 Correct 2 ms 1072 KB Output is correct
41 Correct 35 ms 1400 KB Output is correct
42 Correct 8 ms 3668 KB Output is correct
43 Correct 9 ms 3640 KB Output is correct
44 Correct 7 ms 3764 KB Output is correct
45 Correct 7 ms 3768 KB Output is correct
46 Correct 7 ms 3768 KB Output is correct
47 Correct 10 ms 1840 KB Output is correct
48 Correct 9 ms 2824 KB Output is correct
49 Correct 8 ms 3132 KB Output is correct
50 Correct 8 ms 3156 KB Output is correct
51 Correct 10 ms 2932 KB Output is correct
52 Correct 10 ms 2824 KB Output is correct
53 Correct 7 ms 3768 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 308 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 436 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 440 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Correct 1 ms 312 KB Output is correct
35 Correct 1 ms 312 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 340 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 2 ms 340 KB Output is correct
40 Correct 2 ms 1072 KB Output is correct
41 Correct 35 ms 1400 KB Output is correct
42 Correct 8 ms 3668 KB Output is correct
43 Correct 9 ms 3640 KB Output is correct
44 Correct 7 ms 3764 KB Output is correct
45 Correct 7 ms 3768 KB Output is correct
46 Correct 7 ms 3768 KB Output is correct
47 Correct 10 ms 1840 KB Output is correct
48 Correct 9 ms 2824 KB Output is correct
49 Correct 8 ms 3132 KB Output is correct
50 Correct 8 ms 3156 KB Output is correct
51 Correct 10 ms 2932 KB Output is correct
52 Correct 10 ms 2824 KB Output is correct
53 Correct 7 ms 3768 KB Output is correct
54 Correct 51 ms 16160 KB Output is correct
55 Execution timed out 3072 ms 10952 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 308 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 312 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Execution timed out 3062 ms 23336 KB Time limit exceeded
14 Halted 0 ms 0 KB -