Submission #1021145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021145		Alihan_8	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	390 ms	98696 KiB

copypaste3

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

const int inf = 1e15;

const int Mod = 998244353;

struct _hash{
    vector <int> pw, p;

    _hash() : pw(1, 1) {}

    void modify(string s, int P){
        int n = s.size();

        while ( pw.size() <= n ){
            pw.pb(pw.back() * 1LL * P % Mod);
        }

        p.resize(n + 1);

        for ( int i = 0; i < n; i++ ){
            p[i + 1] = (p[i] * 1LL * P + s[i] - 'a' + 1) % Mod;
        }
    }

    int get(int l, int r){
        return (p[r + 1] - p[l] * 1LL * pw[r - l + 1] % Mod + Mod) % Mod;
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;

    string s; cin >> s;

    int A, B, C; cin >> A >> B >> C;

    _hash h1, h2;

    h1.modify(s, 31);
    h2.modify(s, 47);

    vector <vector<int>> nxt(n + 1, vector <int> (n));

    for ( int l = 1; l <= n; l++ ){
        map <pair<int,int>,int> lst;

        for ( int i = n - l; i >= 0; i-- ){
            int p = i, q = i + l - 1;

            if ( q + l < n ){
                lst[{h1.get(q + 1, q + l), h2.get(q + 1, q + l)}] = q + 1;
            }

            if ( lst.count({h1.get(p, q), h2.get(p, q)}) ){
                nxt[l][i] = lst[{h1.get(p, q), h2.get(p, q)}];
            } else{
                nxt[l][i] = -1;
            }
        }
    }

    vector <vector<int>> dp(n, vector <int> (n, inf));

    for ( int l = 1; l <= n; l++ ){
        for ( int i = 0; i + l <= n; i++ ){
            int p = i, q = i + l - 1;

            chmin(dp[p][q], l * A);

            if ( p + 1 <= q ){
                chmin(dp[p][q], min(dp[p][q - 1], dp[p + 1][q]) + A);
            }

            int j = i, cnt = 1;

            while ( (j = nxt[l][j]) != -1 ){
                ++cnt;

                int r = j + l - 1;

                chmin(dp[i][r], dp[p][q] + (r - i + 1 - l * cnt) * A + B + cnt * C);
            }
        }
    }

    cout << dp[0][n - 1];

    cout << '\n';
}

Compilation message (stderr)

copypaste3.cpp: In member function 'void _hash::modify(std::string, long long int)':
copypaste3.cpp:43:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   43 |         while ( pw.size() <= n ){
      |                 ~~~~~~~~~~^~~~

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