Submission #899062

#	Time	Username	Problem	Language	Result	Execution time	Memory
899062		LucaIlie	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	937 ms	73540 KiB

copypaste3

#include <bits/stdc++.h>

using namespace std;


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

    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:27:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for ( int i = 1; i < t.size(); i++ )
      |                          ~~^~~~~~~~~~
copypaste3.cpp:29:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         for ( int i = 1; i < t.size(); i++ ){
      |                          ~~^~~~~~~~~~
copypaste3.cpp:32:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             while( i + z[i] < t.size() && t[z[i]] == t[i + z[i]] )
      |                    ~~~~~~~~~^~~~~~~~~~
copypaste3.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             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