Submission #899060

#	Time	Username	Problem	Language	Result	Execution time	Memory
899060		LucaIlie	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	967 ms	73612 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;
int z[2 * MAX_N + 2], nextPos[MAX_N + 1][MAX_N + 1];
long long dp[MAX_N + 1][MAX_N + 1];

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 } );

    string t = s;
    for ( int l = n; l >= 1; l-- ) {
        t = s[l] + t;

        int ls = 0, rs = 0;
        for ( int i = 1; i < t.size(); i++ )
            z[i] = 0;
        for ( int i = 1; i < t.size(); i++ ){
            if ( i < rs )
                z[i] = min( z[i - ls], rs - i );
            while( i + z[i] < t.size() && t[z[i]] == t[i + z[i]] )
                z[i]++;
            if ( i + z[i] > rs ) {
                ls = i;
                rs = i + z[i];
            }
        }

        for ( int r = l; r <= n; r++ ) {
            int i = n - l + r + 2;
            while ( i < t.size() && z[i] < r - l + 1 )
                i++;
            nextPos[l][r] = i - (n - l + 1);
        }
    }

    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 = l;
            while ( nextPos[k][k + len - 1] <= n ) {
                cost += (long long)a * (nextPos[k][k + len - 1] - (k + len)) + c;
                k = nextPos[k][k + len - 1];
                dp[l][k + len - 1] = min( dp[l][k + len - 1], cost );
            }
        }
    }

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

    return 0;
}

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:65:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for ( int i = 1; i < t.size(); i++ )
      |                          ~~^~~~~~~~~~
copypaste3.cpp:67:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for ( int i = 1; i < t.size(); i++ ){
      |                          ~~^~~~~~~~~~
copypaste3.cpp:70:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             while( i + z[i] < t.size() && t[z[i]] == t[i + z[i]] )
      |                    ~~~~~~~~~^~~~~~~~~~
copypaste3.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |             while ( i < t.size() && z[i] < r - l + 1 )
      |                     ~~^~~~~~~~~~

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