Submission #574127

#	Time	Username	Problem	Language	Result	Execution time	Memory
574127		chonka	Copy and Paste 3 (JOI22_copypaste3)	C++98	100 / 100	1732 ms	155216 KiB

copypaste3

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int MAXN = 2507 ;
const int BASE = 27 ;

ll MOD[ 2 ] = { 1000000007 , 998244353 } ;

int n ;
string a ;
ll costA , costB , costC ;

struct hsh {
    int l , r ;
    ll val[ 2 ] ;
    void advance ( int nw ) {
        for ( auto i : { 0 , 1 } ) {
            val[ i ] = ( val[ i ] * BASE + nw ) % MOD[ i ] ;
        }
    }
};

hsh aux[ MAXN ][ MAXN ] ;
pair < int , int > nxt[ MAXN ][ MAXN ] ;
ll dp[ MAXN ][ MAXN ] ;

map < pair < ll , ll > , int > w ;
set < int > s[ MAXN ] ;


void input ( ) {
    cin >> n >> a ;
    cin >> costA >> costB >> costC ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        for ( int j = i ; j <= n ; ++ j ) {
            aux[ i ][ j ] = aux[ i ][ j - 1 ] ;
            aux[ i ][ j ].l = i , aux[ i ][ j ].r = j ;
            aux[ i ][ j ].advance ( a[ j - 1 ] - 'a' + 1 ) ;
        }
    }
    for ( int i = 1 ; i <= n + 2 ; ++ i ) {
        for ( int j = i ; j <= n + 2 ; ++ j ) {
            dp[ i ][ j ] = 1e15 ;
        }
    }
    for ( int i = 1 ; i <= n + 2 ; ++ i ) {
        for ( int j = 0 ; j < i ; ++ j ) {
            dp[ i ][ j ] = costB ;
        }
    }
    for ( int len = 0 ; len < n ; ++ len ) {
        w.clear ( ) ;
        for ( int i = 1 ; i + len <= n ; ++ i ) {
            int j = i + len ;
            pair < ll , ll > hh = { aux[ i ][ j ].val[ 0 ] , aux[ i ][ j ].val[ 1 ] } ;
            if ( w[ hh ] == 0 ) { w[ hh ] = i ; }
            s[ w[ hh ] ].insert ( i ) ;
        }
        for ( int i = 1 ; i + len <= n ; ++ i ) {
            int j = i + len ;
            pair < ll , ll > hh = { aux[ i ][ j ].val[ 0 ] , aux[ i ][ j ].val[ 1 ] } ;
            if ( w[ hh ] != i ) { continue ; }
            int id = w[ hh ] ;
            auto pos = s[ id ].begin ( ) ;
            for ( auto x : s[ id ] ) {
                while ( pos != s[ id ].end ( ) && x + len >= *pos ) {
                    ++ pos ;
                }
                if ( pos != s[ id ].end ( ) ) {
                    nxt[ x ][ x + len ] = { *pos , *pos + len } ;
                }
            }
            s[ id ].clear ( ) ;
        }
    }
}

void solve ( ) {
    for ( int len = 0 ; len < n ; ++ len ) {
        for ( int i = 1 ; i + len <= n ; ++ i ) {
            int j = i + len ;
            dp[ i ][ j ] = min ( dp[ i ][ j ] , dp[ i + 1 ][ j ] + costA ) ;
            dp[ i ][ j ] = min ( dp[ i ][ j ] , dp[ i ][ j - 1 ] + costA ) ;
            pair < int , int > act ;
            act = { i , j } ;
            int coef = 1 ;
            while ( 1 ) {
                act = nxt[ act.first ][ act.second ] ;
                if ( act.first <= 0 ) { break ; }
                ++ coef ;
                int lft = ( act.second - i + 1 ) - coef * ( j - i + 1 ) ;
                dp[ i ][ act.second ] = min ( dp[ i ][ act.second ] , dp[ i ][ j ] + coef * costC + lft * costA + costB ) ;
            }
        }
    }
    cout << dp[ 1 ][ n ] - costB << "\n" ;
}


int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t ;
    /// cin >> t ;
    t = 1 ;
    while ( t -- ) {
        input ( ) ;
        solve ( ) ;
    }
    return 0 ;
}

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