Submission #776244

#	Time	Username	Problem	Language	Result	Execution time	Memory
776244		rembocoder	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	681 ms	67620 KiB

copypaste3

#include <bits/stdc++.h>

using namespace std;

#define int int64_t

int mod = 100000000003LL;
int B = 41;
const int inf = 2e18;
const int max_len = 2500;

int h[max_len + 1][max_len + 1];
int dp[max_len + 1][max_len + 1];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    int a, b, c;
    cin >> a >> b >> c;
    for (int l = 0; l <= n; l++) {
        for (int r = l + 1; r <= n; r++) {
            h[l][r] = (h[l][r - 1] * B + s[r - 1] - 'a' + 1) % mod;
        }
    }
    for (int l = 0; l <= n; l++) {
        for (int r = l; r <= n; r++) {
            dp[l][r] = a * (r - l);
        }
    }
    for (int len = 1; len <= n; len++) {
        for (int l = 0, r = len; r <= n; l++, r++) {
            dp[l][r] = min(dp[l][r], dp[l + 1][r] + a);
            dp[l][r] = min(dp[l][r], dp[l][r - 1] + a);
        }
        map<int, vector<int>> where;
        for (int l = 0, r = len; r <= n; l++, r++) {
            where[h[l][r]].push_back(l);
        }
        vector<int> nxt(n, -1);
        for (auto it = where.begin(); it != where.end(); it++) {
            auto& cur_list = it->second;
            int j = 0;
            for (int i = 0; i < cur_list.size(); i++) {
                while (j < cur_list.size() && cur_list[j] - cur_list[i] < len) {
                    j++;
                }
                if (j < cur_list.size()) {
                    nxt[cur_list[i]] = cur_list[j];
                }
            }
        }
        for (int l = 0, r = len; r <= n; l++, r++) {
            int cur = l;
            int cnt = 1;
            while (nxt[cur] != -1) {
                cur = nxt[cur];
                cnt++;
                int R = cur + len;
                dp[l][R] = min(dp[l][cur + len], dp[l][r] + b + c * cnt + a * (R - l - cnt * (r - l)));
            }
        }
    }
    cout << dp[0][n] << '\n';
}

Compilation message (stderr)

copypaste3.cpp: In function 'int32_t main()':
copypaste3.cpp:47:31: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |             for (int i = 0; i < cur_list.size(); i++) {
      |                             ~~^~~~~~~~~~~~~~~~~
copypaste3.cpp:48:26: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |                 while (j < cur_list.size() && cur_list[j] - cur_list[i] < len) {
      |                        ~~^~~~~~~~~~~~~~~~~
copypaste3.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |                 if (j < cur_list.size()) {
      |                     ~~^~~~~~~~~~~~~~~~~

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