Submission #574126

#	Time	Username	Problem	Language	Result	Execution time	Memory
574126		chonka	Copy and Paste 3 (JOI22_copypaste3)	C++98	100 / 100	2385 ms	505316 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 ] ;
vector < hsh > srt ;
int eq_class[ MAXN ][ MAXN ] ;
vector < pair < int , int > > class_list[ MAXN * MAXN ] ;

pair < int , int > nxt[ MAXN ][ MAXN ] ;
ll dp[ MAXN ][ 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 ) ;
            srt.push_back ( aux[ i ][ j ] ) ;
        }
    }
    auto cmp = [ & ] ( hsh p1 , hsh p2 ) {
        for ( auto i : { 0 , 1 } ) {
            if ( p1.val[ i ] != p2.val[ i ] ) {
                return ( p1.val[ i ] < p2.val[ i ] ) ;
            }
        }
        return false ;
    };
    sort ( srt.begin ( ) , srt.end ( ) , cmp ) ;
    int sz = srt.size ( ) ;
    eq_class[ srt[ 0 ].l ][ srt[ 0 ].r ] = 1 ;
    int tp = 1 ;
    for ( int i = 1 ; i < sz ; ++ i ) {
        if ( srt[ i ].val[ 0 ] == srt[ i - 1 ].val[ 0 ] && srt[ i ].val[ 1 ] == srt[ i - 1 ].val[ 1 ] ) {
            eq_class[ srt[ i ].l ][ srt[ i ].r ] = tp ;
        }
        else {
            eq_class[ srt[ i ].l ][ srt[ i ].r ] = ++ tp ;
        }
    }
    for ( int i = 1 ; i <= n + 2 ; ++ i ) {
        for ( int j = i ; j <= n + 2 ; ++ j ) {
            class_list[ eq_class[ i ][ j ] ].push_back ( { i , 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 wh = 1 ; wh <= tp ; ++ wh ) {
        int sz = class_list[ wh ].size ( ) ;
        int pos = 0 ;
        for ( int i = 0 ; i < sz ; ++ i ) {
            while ( pos < sz && class_list[ wh ][ i ].second >= class_list[ wh ][ pos ].first ) {
                ++ pos ;
            }
            if ( pos < sz ) {
                nxt[ class_list[ wh ][ i ].first ][ class_list[ wh ][ i ].second ] = class_list[ wh ][ pos ] ;
            }
            else {
                nxt[ class_list[ wh ][ i ].first ][ class_list[ wh ][ i ].second ] = { -1 , -1 } ;
            }
        }
    }
}

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