Submission #776696

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
776696	2023-07-08T07:26:52 Z	danikoynov	Copy and Paste 3 (JOI22_copypaste3)	C++14	25 / 100	12 ms	3156 KB

copypaste3

/**
 ____ ____ ____ ____ ____ ____
||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 = 210;
const ll base = 29, inf = 1e18;

int n;
ll a, b, c, h[maxn], pw[maxn], dp[maxn][maxn];
string s;
unordered_map < int, vector < int > > occ;
unordered_map < ll, ll > hs_dp;

ll get_hash(int i, int j)
{
    if (i > j)
        return 0;
    return h[j] - h[i - 1] * pw[j - i + 1];
}

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 ++)
            dp[i][j] = inf;

    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);
            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;

            int pos = i;
            while(pos <= n)
            {
                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);
        }

    }

    cout << hs_dp[h[n]] << endl;


}

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

Subtask #1
1.0 / 1.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct
5	Correct	212 KB	Output is correct
6	Correct	212 KB	Output is correct
7	Correct	212 KB	Output is correct
8	Correct	212 KB	Output is correct
9	Correct	212 KB	Output is correct
10	Correct	212 KB	Output is correct

Subtask #2
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Runtime error	1 ms	1108 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-

Subtask #3
14.0 / 14.0

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

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	0 ms	340 KB	Output is correct
25	Correct	1 ms	388 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	1 ms	340 KB	Output is correct
31	Correct	1 ms	340 KB	Output is correct
32	Correct	1 ms	340 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	1 ms	212 KB	Output is correct
35	Correct	1 ms	212 KB	Output is correct
36	Correct	1 ms	212 KB	Output is correct
37	Correct	1 ms	212 KB	Output is correct
38	Correct	0 ms	212 KB	Output is correct
39	Correct	1 ms	340 KB	Output is correct
40	Correct	2 ms	852 KB	Output is correct
41	Correct	8 ms	732 KB	Output is correct
42	Correct	9 ms	3028 KB	Output is correct
43	Correct	9 ms	3028 KB	Output is correct
44	Correct	9 ms	3028 KB	Output is correct
45	Correct	12 ms	3124 KB	Output is correct
46	Correct	9 ms	3156 KB	Output is correct
47	Correct	8 ms	1204 KB	Output is correct
48	Correct	9 ms	2232 KB	Output is correct
49	Correct	8 ms	2516 KB	Output is correct
50	Correct	8 ms	2516 KB	Output is correct
51	Correct	9 ms	2224 KB	Output is correct
52	Correct	9 ms	2224 KB	Output is correct
53	Correct	10 ms	3156 KB	Output is correct

Subtask #5
0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	0 ms	340 KB	Output is correct
25	Correct	1 ms	388 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	1 ms	340 KB	Output is correct
31	Correct	1 ms	340 KB	Output is correct
32	Correct	1 ms	340 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	1 ms	212 KB	Output is correct
35	Correct	1 ms	212 KB	Output is correct
36	Correct	1 ms	212 KB	Output is correct
37	Correct	1 ms	212 KB	Output is correct
38	Correct	0 ms	212 KB	Output is correct
39	Correct	1 ms	340 KB	Output is correct
40	Correct	2 ms	852 KB	Output is correct
41	Correct	8 ms	732 KB	Output is correct
42	Correct	9 ms	3028 KB	Output is correct
43	Correct	9 ms	3028 KB	Output is correct
44	Correct	9 ms	3028 KB	Output is correct
45	Correct	12 ms	3124 KB	Output is correct
46	Correct	9 ms	3156 KB	Output is correct
47	Correct	8 ms	1204 KB	Output is correct
48	Correct	9 ms	2232 KB	Output is correct
49	Correct	8 ms	2516 KB	Output is correct
50	Correct	8 ms	2516 KB	Output is correct
51	Correct	9 ms	2224 KB	Output is correct
52	Correct	9 ms	2224 KB	Output is correct
53	Correct	10 ms	3156 KB	Output is correct
54	Runtime error	1 ms	1108 KB	Execution killed with signal 11
55	Halted	0 ms	0 KB	-

Subtask #6
0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Runtime error	1 ms	1108 KB	Execution killed with signal 11
14	Halted	0 ms	0 KB	-

Submission #776696

Compilation message

Subtask #1 1.0 / 1.0

Subtask #2 0 / 5.0

Subtask #3 14.0 / 14.0

Subtask #4 10.0 / 10.0

Subtask #5 0 / 32.0

Subtask #6 0 / 38.0

Subtask #1
1.0 / 1.0

Subtask #2
0 / 5.0

Subtask #3
14.0 / 14.0

Subtask #4
10.0 / 10.0

Subtask #5
0 / 32.0

Subtask #6
0 / 38.0