답안 #1060965

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1060965	2024-08-16T05:04:39 Z	sleepntsheep	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	2249 ms	173056 KB

copypaste3

#pragma GCC optimize("O3,unroll-loops")

#include <string>
#include <iostream>
#include <map>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
template <typename T>
using ve = vector<T>;
template <typename T>
using bs = basic_string<T>;

const int N = 2505;
const ll B = 137, M = 1000000007,
      B2 = 141, M2 = 1000000009;

int n;
ll dp[N][N], a, b, c;
char s[N];

ll hs[N], bp[N], ibp[N], bp2[N], ibp2[N], hs2[N];

ll bpow(ll a, ll b, ll m) {
    if (!b) return 1;
    ll r { bpow(a, b / 2, m) };
    if (b & 1) return r * r % m * a % m;
    return r * r % m;
}

void do_hash() {
    bp[0] = ibp[0] = bp2[0] = ibp2[0] = 1;
    for (int i = 1; i <= n; ++i) bp[i] = bp[i - 1] * B % M, ibp[i] = bpow(bp[i], M - 2, M);
    for (int i = 1; i <= n; ++i) hs[i] = bp[i] * (s[i] - 'a' + 1) % M, hs[i] = (hs[i] + hs[i - 1]) % M;

    for (int i = 1; i <= n; ++i) bp2[i] = bp2[i - 1] * B2 % M2, ibp2[i] = bpow(bp2[i], M2 - 2, M2);
    for (int i = 1; i <= n; ++i) hs2[i] = bp2[i] * (s[i] - 'a' + 1) % M2, hs2[i] = (hs2[i] + hs2[i - 1]) % M2;
}

inline ll get_hash(int l, int r) {
    return (ibp[l] * (hs[r] - hs[l - 1] + M) % M) * (ibp2[l] * (hs2[r] - hs2[l - 1] + M2) % M2);
}

ve<ll> chocolate;

ve<bs<int>> oo;

int get_pos(int l, int r) {
    return lower_bound(chocolate.begin(), chocolate.end(), get_hash(l, r)) - chocolate.begin();
}

void init() {
    do_hash();
    memset(dp, 63, sizeof dp);

    for (int i = 1; i <= n; ++i) {
        dp[i][i] = a;
        for (int j = i; j <= n; ++j) 
            chocolate.push_back(get_hash(i, j));
    }

    sort(chocolate.begin(), chocolate.end());
    chocolate.erase(unique(chocolate.begin(), chocolate.end()), chocolate.end());
    oo = ve<bs<int>>(chocolate.size());
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; ++j) 
            oo[get_pos(i, j)].push_back(i);
}

int main() {
    scanf("%d%s%lld%lld%lld", &n, s + 1, &a, &b, &c);

    init();

    for (int l = 1; l <= n; ++l) {
        for (int i = 1, j = l; j <= n; ++i, ++j) {
            if (i < j) dp[i][j] = min(dp[i][j], dp[i + 1][j] + a);
            if (j > i) dp[i][j] = min(dp[i][j], dp[i][j - 1] + a);

            auto &oc = oo[get_pos(i, j)];
            auto it = lower_bound(oc.begin(), oc.end(), i);
            int cnt = 1;
            for (; it != oc.end(); ++cnt) {
                int jj = *it + l - 1;
                dp[i][jj] = min(dp[i][jj], dp[i][j] + b + cnt * c + (jj - i + 1 - cnt * l) * a);
                it = lower_bound(next(it), oc.end(), *it + l);
            }
        }
    }

    printf("%lld", dp[1][n]);
}

Compilation message

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%d%s%lld%lld%lld", &n, s + 1, &a, &b, &c);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	49496 KB	Output is correct
2	Correct	7 ms	49500 KB	Output is correct
3	Correct	7 ms	49500 KB	Output is correct
4	Correct	6 ms	49500 KB	Output is correct
5	Correct	6 ms	49500 KB	Output is correct
6	Correct	7 ms	49500 KB	Output is correct
7	Correct	6 ms	49456 KB	Output is correct
8	Correct	6 ms	49500 KB	Output is correct
9	Correct	7 ms	49500 KB	Output is correct
10	Correct	7 ms	49500 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	49496 KB	Output is correct
2	Correct	7 ms	49500 KB	Output is correct
3	Correct	371 ms	73788 KB	Output is correct
4	Correct	460 ms	76968 KB	Output is correct
5	Correct	521 ms	84416 KB	Output is correct
6	Correct	614 ms	87552 KB	Output is correct
7	Correct	747 ms	92312 KB	Output is correct
8	Correct	741 ms	93088 KB	Output is correct
9	Correct	732 ms	92320 KB	Output is correct
10	Correct	6 ms	49500 KB	Output is correct
11	Correct	6 ms	49500 KB	Output is correct
12	Correct	6 ms	49500 KB	Output is correct
13	Correct	7 ms	49500 KB	Output is correct
14	Correct	6 ms	49472 KB	Output is correct
15	Correct	6 ms	49500 KB	Output is correct
16	Correct	6 ms	49448 KB	Output is correct
17	Correct	6 ms	49500 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	49496 KB	Output is correct
2	Correct	7 ms	49500 KB	Output is correct
3	Correct	7 ms	49500 KB	Output is correct
4	Correct	6 ms	49500 KB	Output is correct
5	Correct	6 ms	49500 KB	Output is correct
6	Correct	7 ms	49500 KB	Output is correct
7	Correct	6 ms	49456 KB	Output is correct
8	Correct	6 ms	49500 KB	Output is correct
9	Correct	7 ms	49500 KB	Output is correct
10	Correct	7 ms	49500 KB	Output is correct
11	Correct	7 ms	49500 KB	Output is correct
12	Correct	7 ms	49452 KB	Output is correct
13	Correct	6 ms	49500 KB	Output is correct
14	Correct	6 ms	49360 KB	Output is correct
15	Correct	6 ms	49480 KB	Output is correct
16	Correct	6 ms	49500 KB	Output is correct
17	Correct	7 ms	49500 KB	Output is correct
18	Correct	7 ms	49500 KB	Output is correct
19	Correct	6 ms	49504 KB	Output is correct
20	Correct	7 ms	49500 KB	Output is correct
21	Correct	7 ms	49500 KB	Output is correct
22	Correct	7 ms	49500 KB	Output is correct
23	Correct	7 ms	49412 KB	Output is correct
24	Correct	6 ms	49500 KB	Output is correct
25	Correct	7 ms	49500 KB	Output is correct
26	Correct	6 ms	49500 KB	Output is correct
27	Correct	6 ms	49456 KB	Output is correct
28	Correct	6 ms	49500 KB	Output is correct
29	Correct	6 ms	49500 KB	Output is correct
30	Correct	7 ms	49752 KB	Output is correct
31	Correct	6 ms	49496 KB	Output is correct
32	Correct	6 ms	49500 KB	Output is correct
33	Correct	6 ms	49500 KB	Output is correct
34	Correct	6 ms	49420 KB	Output is correct
35	Correct	6 ms	49500 KB	Output is correct
36	Correct	6 ms	49500 KB	Output is correct
37	Correct	6 ms	49500 KB	Output is correct
38	Correct	6 ms	49500 KB	Output is correct
39	Correct	7 ms	49496 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	49496 KB	Output is correct
2	Correct	7 ms	49500 KB	Output is correct
3	Correct	7 ms	49500 KB	Output is correct
4	Correct	6 ms	49500 KB	Output is correct
5	Correct	6 ms	49500 KB	Output is correct
6	Correct	7 ms	49500 KB	Output is correct
7	Correct	6 ms	49456 KB	Output is correct
8	Correct	6 ms	49500 KB	Output is correct
9	Correct	7 ms	49500 KB	Output is correct
10	Correct	7 ms	49500 KB	Output is correct
11	Correct	7 ms	49500 KB	Output is correct
12	Correct	7 ms	49452 KB	Output is correct
13	Correct	6 ms	49500 KB	Output is correct
14	Correct	6 ms	49360 KB	Output is correct
15	Correct	6 ms	49480 KB	Output is correct
16	Correct	6 ms	49500 KB	Output is correct
17	Correct	7 ms	49500 KB	Output is correct
18	Correct	7 ms	49500 KB	Output is correct
19	Correct	6 ms	49504 KB	Output is correct
20	Correct	7 ms	49500 KB	Output is correct
21	Correct	7 ms	49500 KB	Output is correct
22	Correct	7 ms	49500 KB	Output is correct
23	Correct	7 ms	49412 KB	Output is correct
24	Correct	6 ms	49500 KB	Output is correct
25	Correct	7 ms	49500 KB	Output is correct
26	Correct	6 ms	49500 KB	Output is correct
27	Correct	6 ms	49456 KB	Output is correct
28	Correct	6 ms	49500 KB	Output is correct
29	Correct	6 ms	49500 KB	Output is correct
30	Correct	7 ms	49752 KB	Output is correct
31	Correct	6 ms	49496 KB	Output is correct
32	Correct	6 ms	49500 KB	Output is correct
33	Correct	6 ms	49500 KB	Output is correct
34	Correct	6 ms	49420 KB	Output is correct
35	Correct	6 ms	49500 KB	Output is correct
36	Correct	6 ms	49500 KB	Output is correct
37	Correct	6 ms	49500 KB	Output is correct
38	Correct	6 ms	49500 KB	Output is correct
39	Correct	7 ms	49496 KB	Output is correct
40	Correct	7 ms	49500 KB	Output is correct
41	Correct	11 ms	49888 KB	Output is correct
42	Correct	13 ms	50392 KB	Output is correct
43	Correct	12 ms	50392 KB	Output is correct
44	Correct	13 ms	50388 KB	Output is correct
45	Correct	13 ms	50392 KB	Output is correct
46	Correct	11 ms	50392 KB	Output is correct
47	Correct	11 ms	49880 KB	Output is correct
48	Correct	11 ms	50136 KB	Output is correct
49	Correct	12 ms	50136 KB	Output is correct
50	Correct	12 ms	50136 KB	Output is correct
51	Correct	12 ms	50132 KB	Output is correct
52	Correct	12 ms	50132 KB	Output is correct
53	Correct	12 ms	50392 KB	Output is correct

Subtask #5
32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	49496 KB	Output is correct
2	Correct	7 ms	49500 KB	Output is correct
3	Correct	7 ms	49500 KB	Output is correct
4	Correct	6 ms	49500 KB	Output is correct
5	Correct	6 ms	49500 KB	Output is correct
6	Correct	7 ms	49500 KB	Output is correct
7	Correct	6 ms	49456 KB	Output is correct
8	Correct	6 ms	49500 KB	Output is correct
9	Correct	7 ms	49500 KB	Output is correct
10	Correct	7 ms	49500 KB	Output is correct
11	Correct	7 ms	49500 KB	Output is correct
12	Correct	7 ms	49452 KB	Output is correct
13	Correct	6 ms	49500 KB	Output is correct
14	Correct	6 ms	49360 KB	Output is correct
15	Correct	6 ms	49480 KB	Output is correct
16	Correct	6 ms	49500 KB	Output is correct
17	Correct	7 ms	49500 KB	Output is correct
18	Correct	7 ms	49500 KB	Output is correct
19	Correct	6 ms	49504 KB	Output is correct
20	Correct	7 ms	49500 KB	Output is correct
21	Correct	7 ms	49500 KB	Output is correct
22	Correct	7 ms	49500 KB	Output is correct
23	Correct	7 ms	49412 KB	Output is correct
24	Correct	6 ms	49500 KB	Output is correct
25	Correct	7 ms	49500 KB	Output is correct
26	Correct	6 ms	49500 KB	Output is correct
27	Correct	6 ms	49456 KB	Output is correct
28	Correct	6 ms	49500 KB	Output is correct
29	Correct	6 ms	49500 KB	Output is correct
30	Correct	7 ms	49752 KB	Output is correct
31	Correct	6 ms	49496 KB	Output is correct
32	Correct	6 ms	49500 KB	Output is correct
33	Correct	6 ms	49500 KB	Output is correct
34	Correct	6 ms	49420 KB	Output is correct
35	Correct	6 ms	49500 KB	Output is correct
36	Correct	6 ms	49500 KB	Output is correct
37	Correct	6 ms	49500 KB	Output is correct
38	Correct	6 ms	49500 KB	Output is correct
39	Correct	7 ms	49496 KB	Output is correct
40	Correct	7 ms	49500 KB	Output is correct
41	Correct	11 ms	49888 KB	Output is correct
42	Correct	13 ms	50392 KB	Output is correct
43	Correct	12 ms	50392 KB	Output is correct
44	Correct	13 ms	50388 KB	Output is correct
45	Correct	13 ms	50392 KB	Output is correct
46	Correct	11 ms	50392 KB	Output is correct
47	Correct	11 ms	49880 KB	Output is correct
48	Correct	11 ms	50136 KB	Output is correct
49	Correct	12 ms	50136 KB	Output is correct
50	Correct	12 ms	50136 KB	Output is correct
51	Correct	12 ms	50132 KB	Output is correct
52	Correct	12 ms	50132 KB	Output is correct
53	Correct	12 ms	50392 KB	Output is correct
54	Correct	40 ms	53452 KB	Output is correct
55	Correct	103 ms	56504 KB	Output is correct
56	Correct	211 ms	69048 KB	Output is correct
57	Correct	210 ms	69020 KB	Output is correct
58	Correct	207 ms	69044 KB	Output is correct
59	Correct	213 ms	69052 KB	Output is correct
60	Correct	217 ms	69048 KB	Output is correct
61	Correct	207 ms	61876 KB	Output is correct
62	Correct	110 ms	56500 KB	Output is correct
63	Correct	208 ms	66328 KB	Output is correct
64	Correct	206 ms	66132 KB	Output is correct
65	Correct	196 ms	62900 KB	Output is correct
66	Correct	200 ms	62900 KB	Output is correct
67	Correct	203 ms	69312 KB	Output is correct

Subtask #6
38.0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	49496 KB	Output is correct
2	Correct	7 ms	49500 KB	Output is correct
3	Correct	7 ms	49500 KB	Output is correct
4	Correct	6 ms	49500 KB	Output is correct
5	Correct	6 ms	49500 KB	Output is correct
6	Correct	7 ms	49500 KB	Output is correct
7	Correct	6 ms	49456 KB	Output is correct
8	Correct	6 ms	49500 KB	Output is correct
9	Correct	7 ms	49500 KB	Output is correct
10	Correct	7 ms	49500 KB	Output is correct
11	Correct	7 ms	49496 KB	Output is correct
12	Correct	7 ms	49500 KB	Output is correct
13	Correct	371 ms	73788 KB	Output is correct
14	Correct	460 ms	76968 KB	Output is correct
15	Correct	521 ms	84416 KB	Output is correct
16	Correct	614 ms	87552 KB	Output is correct
17	Correct	747 ms	92312 KB	Output is correct
18	Correct	741 ms	93088 KB	Output is correct
19	Correct	732 ms	92320 KB	Output is correct
20	Correct	6 ms	49500 KB	Output is correct
21	Correct	6 ms	49500 KB	Output is correct
22	Correct	6 ms	49500 KB	Output is correct
23	Correct	7 ms	49500 KB	Output is correct
24	Correct	6 ms	49472 KB	Output is correct
25	Correct	6 ms	49500 KB	Output is correct
26	Correct	6 ms	49448 KB	Output is correct
27	Correct	6 ms	49500 KB	Output is correct
28	Correct	7 ms	49500 KB	Output is correct
29	Correct	7 ms	49452 KB	Output is correct
30	Correct	6 ms	49500 KB	Output is correct
31	Correct	6 ms	49360 KB	Output is correct
32	Correct	6 ms	49480 KB	Output is correct
33	Correct	6 ms	49500 KB	Output is correct
34	Correct	7 ms	49500 KB	Output is correct
35	Correct	7 ms	49500 KB	Output is correct
36	Correct	6 ms	49504 KB	Output is correct
37	Correct	7 ms	49500 KB	Output is correct
38	Correct	7 ms	49500 KB	Output is correct
39	Correct	7 ms	49500 KB	Output is correct
40	Correct	7 ms	49412 KB	Output is correct
41	Correct	6 ms	49500 KB	Output is correct
42	Correct	7 ms	49500 KB	Output is correct
43	Correct	6 ms	49500 KB	Output is correct
44	Correct	6 ms	49456 KB	Output is correct
45	Correct	6 ms	49500 KB	Output is correct
46	Correct	6 ms	49500 KB	Output is correct
47	Correct	7 ms	49752 KB	Output is correct
48	Correct	6 ms	49496 KB	Output is correct
49	Correct	6 ms	49500 KB	Output is correct
50	Correct	6 ms	49500 KB	Output is correct
51	Correct	6 ms	49420 KB	Output is correct
52	Correct	6 ms	49500 KB	Output is correct
53	Correct	6 ms	49500 KB	Output is correct
54	Correct	6 ms	49500 KB	Output is correct
55	Correct	6 ms	49500 KB	Output is correct
56	Correct	7 ms	49496 KB	Output is correct
57	Correct	7 ms	49500 KB	Output is correct
58	Correct	11 ms	49888 KB	Output is correct
59	Correct	13 ms	50392 KB	Output is correct
60	Correct	12 ms	50392 KB	Output is correct
61	Correct	13 ms	50388 KB	Output is correct
62	Correct	13 ms	50392 KB	Output is correct
63	Correct	11 ms	50392 KB	Output is correct
64	Correct	11 ms	49880 KB	Output is correct
65	Correct	11 ms	50136 KB	Output is correct
66	Correct	12 ms	50136 KB	Output is correct
67	Correct	12 ms	50136 KB	Output is correct
68	Correct	12 ms	50132 KB	Output is correct
69	Correct	12 ms	50132 KB	Output is correct
70	Correct	12 ms	50392 KB	Output is correct
71	Correct	40 ms	53452 KB	Output is correct
72	Correct	103 ms	56504 KB	Output is correct
73	Correct	211 ms	69048 KB	Output is correct
74	Correct	210 ms	69020 KB	Output is correct
75	Correct	207 ms	69044 KB	Output is correct
76	Correct	213 ms	69052 KB	Output is correct
77	Correct	217 ms	69048 KB	Output is correct
78	Correct	207 ms	61876 KB	Output is correct
79	Correct	110 ms	56500 KB	Output is correct
80	Correct	208 ms	66328 KB	Output is correct
81	Correct	206 ms	66132 KB	Output is correct
82	Correct	196 ms	62900 KB	Output is correct
83	Correct	200 ms	62900 KB	Output is correct
84	Correct	203 ms	69312 KB	Output is correct
85	Correct	708 ms	100164 KB	Output is correct
86	Correct	2043 ms	172444 KB	Output is correct
87	Correct	2153 ms	172180 KB	Output is correct
88	Correct	2249 ms	171892 KB	Output is correct
89	Correct	2076 ms	172936 KB	Output is correct
90	Correct	2090 ms	172180 KB	Output is correct
91	Correct	1073 ms	99744 KB	Output is correct
92	Correct	852 ms	92244 KB	Output is correct
93	Correct	1843 ms	151200 KB	Output is correct
94	Correct	1891 ms	152500 KB	Output is correct
95	Correct	1733 ms	133276 KB	Output is correct
96	Correct	1705 ms	133536 KB	Output is correct
97	Correct	2004 ms	173056 KB	Output is correct

답안 #1060965

Compilation message

Subtask #1 1.0 / 1.0

Subtask #2 5.0 / 5.0

Subtask #3 14.0 / 14.0

Subtask #4 10.0 / 10.0

Subtask #5 32.0 / 32.0

Subtask #6 38.0 / 38.0

Subtask #1
1.0 / 1.0

Subtask #2
5.0 / 5.0

Subtask #3
14.0 / 14.0

Subtask #4
10.0 / 10.0

Subtask #5
32.0 / 32.0

Subtask #6
38.0 / 38.0