oj.uz

Submission #555508

# Submission time Handle Problem Language Result Execution time Memory
555508 2022-05-01T06:43:47 Z tht2005 Copy and Paste 3 (JOI22_copypaste3) C++17
15 / 100
 3000 ms 21876 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

void ckmin(LL& a, LL b) {
    if(a > b) {
        a = b;
    }
}

const int N = 2503;
const int B = 311;
const LL INF = 0x3f3f3f3f3f3f3f3f;

int n, a, b, c, g[N][N];
char s[N];
LL f[N][N], dp[N];
ULL h[N], pw[N];

ULL get(int l, int r) {
    return h[r] - h[l] * pw[r - l];
}

int main() {
    scanf("%d %s %d %d %d", &n, s, &a, &b, &c);
    h[0] = 0;
    pw[0] = 1;
    for(int i = 0; i < n; ++i) {
        h[i + 1] = h[i] * B + s[i];
        pw[i + 1] = pw[i] * B;
    }
    for(int i = n; i--; ) {
        for(int j = i + 1; j <= n; ++j) {
            g[i][j] = (j + j - i <= n && get(i, j) == get(j, j + j - i)) ? g[j][j + j - i] + 1 : 1;
        }
    }
    for(int i = 0; i < n; ++i) {
        f[i][i + 1] = a + b;
    }
    for(int L = 2; L <= n; ++L) {
        for(int i = 0, j = L; j <= n; ++i, ++j) {
            f[i][j] = (LL)a * L;
            for(int l = i; l < j; ++l) {
                for(int r = l + 1; r <= j; ++r) {
                    dp[i] = 0;
                    for(int k = i + 1; k <= j; ++k) {
                        dp[k] = INF;
                    }
                    for(int k = i; k < j; ++k) {
                        ckmin(dp[k + 1], dp[k] + a);
                        if(k + r - l <= j && get(l, r) == get(k, k + r - l)) ckmin(dp[k + r - l], dp[k] + c);
                    }
                    f[i][j] = min(f[i][j], f[l][r] + dp[j]);
                }
            }
            f[i][j] += b;
        }
    }
    printf("%lld", f[0][n] - b);
    return 0;
}

Compilation message

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

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 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 0 ms 340 KB Output is correct
3 Execution timed out 3058 ms 21876 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 468 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 0 ms 340 KB Output is correct
21 Correct 3 ms 468 KB Output is correct
22 Correct 4 ms 468 KB Output is correct
23 Correct 3 ms 468 KB Output is correct
24 Correct 3 ms 468 KB Output is correct
25 Correct 3 ms 468 KB Output is correct
26 Correct 3 ms 468 KB Output is correct
27 Correct 3 ms 468 KB Output is correct
28 Correct 3 ms 468 KB Output is correct
29 Correct 3 ms 468 KB Output is correct
30 Correct 3 ms 468 KB Output is correct
31 Correct 3 ms 468 KB Output is correct
32 Correct 4 ms 468 KB Output is correct
33 Correct 4 ms 468 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 3 ms 568 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 468 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 0 ms 340 KB Output is correct
21 Correct 3 ms 468 KB Output is correct
22 Correct 4 ms 468 KB Output is correct
23 Correct 3 ms 468 KB Output is correct
24 Correct 3 ms 468 KB Output is correct
25 Correct 3 ms 468 KB Output is correct
26 Correct 3 ms 468 KB Output is correct
27 Correct 3 ms 468 KB Output is correct
28 Correct 3 ms 468 KB Output is correct
29 Correct 3 ms 468 KB Output is correct
30 Correct 3 ms 468 KB Output is correct
31 Correct 3 ms 468 KB Output is correct
32 Correct 4 ms 468 KB Output is correct
33 Correct 4 ms 468 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 3 ms 568 KB Output is correct
40 Correct 414 ms 1016 KB Output is correct
41 Execution timed out 3096 ms 2044 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 468 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 0 ms 340 KB Output is correct
21 Correct 3 ms 468 KB Output is correct
22 Correct 4 ms 468 KB Output is correct
23 Correct 3 ms 468 KB Output is correct
24 Correct 3 ms 468 KB Output is correct
25 Correct 3 ms 468 KB Output is correct
26 Correct 3 ms 468 KB Output is correct
27 Correct 3 ms 468 KB Output is correct
28 Correct 3 ms 468 KB Output is correct
29 Correct 3 ms 468 KB Output is correct
30 Correct 3 ms 468 KB Output is correct
31 Correct 3 ms 468 KB Output is correct
32 Correct 4 ms 468 KB Output is correct
33 Correct 4 ms 468 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 3 ms 568 KB Output is correct
40 Correct 414 ms 1016 KB Output is correct
41 Execution timed out 3096 ms 2044 KB Time limit exceeded
42 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

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