Submission #637164

#	Time	Username	Problem	Language	Result	Execution time	Memory
637164		tht2005	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	543 ms	54008 KiB

copypaste3

#include <bits/stdc++.h>

using namespace std;

template<typename T> void ckmin(T& a, T b) {
    if(a > b) {
        a = b;
    }
}

#define LL long long

#define N 2503

void calc_z(char* s, int n, int* z) {
    z[0] = n;
    for(int i = 1, l = 0, r = 0; i < n; ++i) {
        int k = (i > r) ? 0 : min(z[i - l], r - i + 1);
        while(i + k < n && s[k] == s[i + k]) {
            ++k;
        }
        z[i] = k--;
        if(r < i + k) {
            l = i;
            r = i + k;
        }
    }
}

int n, A, B, C, z[N], nxt[N][N];
char s[N];
LL f[N][N];

int main() {
    scanf("%d %s %d %d %d", &n, s, &A, &B, &C);
    for(int i = 0, k; i < n; ++i) {
        calc_z(s + i, n - i, z + i);
        k = i;
        for(int j = i + 1; j < n; ++j) {
            while(k < j && z[j] >= k + 1 - i) {
                nxt[i][++k] = j;
            }
        }
        while(k < n) {
            nxt[i][++k] = -1;
        }
    }
    for(int i = 0; i < n; ++i) {
        for(int j = i; j <= n; ++j) {
            f[i][j] = (long long)A * (j - i);
        }
    }
    for(int L = 1; L < n; ++L) {
        for(int i = 0, j = L; j <= n; ++i, ++j) {
            if(i) {
                ckmin(f[i - 1][j], f[i][j] + A);
            }
            if(j != n) {
                ckmin(f[i][j + 1], f[i][j] + A);
            }
            long long cost = f[i][j] + B + C;
            int x = i;
            while(1) {
                int y = nxt[x][x + L];
                if(y == -1) {
                    break;
                }
                cost += (long long)A * (y - x - L) + C;
                x = y;
                ckmin(f[i][x + L], cost);
            }
        }
    }
    printf("%lld", f[0][n]);
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 1 / 1
• Subtask 2: 5 / 5
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 32 / 32
• Subtask 6: 38 / 38