Submission #555513

#	Time	Username	Problem	Language	Result	Execution time	Memory
555513		tht2005	Copy and Paste 3 (JOI22_copypaste3)	C++17	25 / 100	3094 ms	20692 KiB

copypaste3

#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;
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 = 0; i < n; ++i) {
        for(int j = i + 1; j <= n; ++j) {
            f[i][j] = (LL)a * (j - i);
        }
    }
    for(int L = 1; L < n; ++L) {
        for(int i = 0, j = L; j <= n; ++i, ++j) {
            f[i][j] += b;
            for(int l = 0; l <= i; ++l) {
                dp[l] = 0;
                for(int k = l + 1; k <= n; ++k) {
                    dp[k] = INF;
                }
                for(int k = l; k < n; ++k) {
                    ckmin(dp[k + 1], dp[k] + a);
                    if(k + j - i <= n && get(i, j) == get(k, k + j - i)) ckmin(dp[k + j - i], dp[k] + c);
                }
                for(int r = j + (l == i); r <= n; ++r) {
                    ckmin(f[l][r], f[i][j] + dp[r]);
                }
            }
        }
    }
    printf("%lld", f[0][n]);
    return 0;
}

Compilation message (stderr)

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 / 1
• Subtask 2: 0 / 5
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 0 / 32
• Subtask 6: 0 / 38