Submission #899031

#	Time	Username	Problem	Language	Result	Execution time	Memory
899031		LucaIlie	Copy and Paste 3 (JOI22_copypaste3)	C++17	25 / 100	3069 ms	97064 KiB

copypaste3

#include <bits/stdc++.h>

using namespace std;

struct hashCode {
    int n, nrHashes;
    vector<int> mod;
    vector<vector<int>> p, hashPref;

    void init( string s, vector<int> vals, vector<int> _mod ) {
        n = s.size() - 1;
        nrHashes = vals.size();
        mod = _mod;

        p.resize( nrHashes );
        for ( int h = 0; h < nrHashes; h++ ) {
            p[h].resize( n + 1 );
            p[h][0] = 1;
            for ( int i = 1; i <= n; i++ ) {
                p[h][i] = (long long)p[h][i - 1] * vals[h] % mod[h];
            }
        }

        hashPref.resize( nrHashes );
        for ( int h = 0; h < nrHashes; h++ ) {
            hashPref[h].resize( n + 1 );
            hashPref[h][0] = 1;
            for ( int i = 1; i <= n; i++ )
                hashPref[h][i] = (hashPref[h][i - 1] + (long long)p[h][i - 1] * (s[i] - 'a')) % mod[h];
        }
    }

    vector<int> query( int l, int r ) {
        vector<int> ans;
        for ( int h = 0; h < nrHashes; h++ )
            ans.push_back( (long long)(hashPref[h][r] - hashPref[h][l - 1] + mod[h]) % mod[h] * p[h][n - l] % mod[h] );
        return ans;
    }
} sir;

const int MAX_N = 2500;
long long dp[MAX_N][MAX_N];

int main() {
    int n, a, b, c;
    string s;

    cin >> n >> s >> a >> b >> c;
    s = "#" + s;

    for ( int l = 1; l <= n; l++ ) {
        for ( int r = l; r <= n; r++ )
            dp[l][r] = (long long)a * (r - l + 1) + b;
    }

    int mod1 = (1e9 + 7), mod2 = (1e9 + 9);
    sir.init( s, { 29, 31 }, { mod1, mod2 } );

    for ( int len = 1; len <= n; len++ ) {
        for ( int l = 1; l <= n - len + 1; l++ ) {
            int r = l + len - 1;

            dp[l - 1][r] = min( dp[l - 1][r], dp[l][r] + a );
            dp[l][r + 1] = min( dp[l][r + 1], dp[l][r] + a );

            long long cost = dp[l][r] + b + c;
            int k = r + len;
            while ( k <= n ) {
                if ( sir.query( l, r ) == sir.query( k - len + 1, k ) ) {
                    cost += c;
                    dp[l][k] = min( dp[l][k], cost );
                    k += len;
                } else {
                    cost += a;
                    k++;
                }
            }
        }
    }

    cout << dp[1][n] - b << "\n";

    return 0;
}

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