Submission #547014

#	Time	Username	Problem	Language	Result	Execution time	Memory
547014		ngrace	Copy and Paste 3 (JOI22_copypaste3)	C++14	57 / 100	3120 ms	591468 KiB

copypaste3

#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <string>
using namespace std;
#define v vector
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second

int main(){
    int N;
    cin>>N;
    string S;
    cin>>S;
    ll A,B,C;
    cin>>A>>B>>C;

    //non disjoint next occurence
    v<v<v<int>>> immediateNext(N+1,v<v<int>>(N+1,v<int>(20,N)));
    for(int l=0; l<N; l++){
        for(int i=l+1; i<N; i++){
            if(S[l]==S[i]){
                immediateNext[l][1][0]=i;
                break;
            }
        }
    }
    for(int s=2; s<=N; s++){
        for(int l=0; l<=N-s; l++){
            int nex=immediateNext[l][s-1][0];
            while(nex<=N-s){
                if(S[l+s-1]==S[nex+s-1]){
                    immediateNext[l][s][0]=nex;
                    break;
                }
                nex=immediateNext[nex][s-1][0];
            }
        }
    }
    //make jump pointers:
    for(int i=1; i<20; i++){
        for(int s=2; s<=N; s++){
            for(int l=0; l<=N-s; l++){
                immediateNext[l][s][i]=immediateNext[immediateNext[l][s][i-1]][s][i-1];
            }
        }
    }

    //make next occurence disjoint using jump pointers
    v<v<int>> nextOccur(N, v<int>(N+1, N));
    for(int l=0; l<N; l++){
        for(int s=1; s<=N-l; s++){
            int nex=l;
            for(int i=19; i>=0; i--){
                if(immediateNext[nex][s][i]<l+s){
                    nex=immediateNext[nex][s][i];
                }
            }
            nextOccur[l][s] = immediateNext[nex][s][0];
        }
    }
    

    v<v<ll>> dp(N, v<ll>(N,1e17));
    for(int s=1; s<=N; s++){
        for(int l=N-1; l>=0; l--){
            dp[l][l]=A;
            if(s!=1 && l+s-1<N){
                dp[l][l+s-1] = min(dp[l][l+s-1], A+dp[l+1][l+s-1]);
                dp[l][l+s-1] = min(dp[l][l+s-1], dp[l][l+s-1-1]+A);
            }
            int num=2, nex=nextOccur[l][s];
            while(nex<N){
                int r=nex+s-1;
                dp[l][r] = min(dp[l][r], dp[l][l+s-1]+B+C*num+(r-l+1 - num*s)*A);
                dp[l][r] = min(dp[l][r], A+dp[l+1][r]);
                dp[l][r] = min(dp[l][r], dp[l][r-1]+A);
                nex=nextOccur[nex][s];
                num++;
            }
        }
    }

    cout<<dp[0][N-1]<<endl;
}

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