Submission #896060

#	Time	Username	Problem	Language	Result	Execution time	Memory
896060		alexander707070	Copy and Paste 3 (JOI22_copypaste3)	C++14	25 / 100	5 ms	1720 KiB

copypaste3

#include<bits/stdc++.h>
#define MAXN 207
using namespace std;
 
const long long inf=1e15;
const long long mod=1000000000100011;
 
int n,len;
long long a,b,c,curr;
char s[MAXN];
 
long long dp[MAXN][MAXN];
bool li[MAXN][MAXN];
long long hesh,power;
int nxt[MAXN][MAXN];

long long cost(long long len,long long cnt,long long sz){
    return (len-cnt*sz)*a+cnt*c;
}

unordered_map<long long, vector<int> > last;
unordered_map<long long, int > pt; 

void calc_dp(){
    for(int i=1;i<=n;i++){
        for(int f=1;f<=n;f++){
            dp[i][f]=inf;
        }
    }

    for(int len=1;len<=n;len++){
        for(int s=1;s+len-1<=n;s++){
            int l=s,r=s+len-1;

            if(len==1)dp[l][r]=a;

            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 cnt=0;

            for(int k=s;k<=n;k=nxt[k][k+len-1]){
                cnt++;
                dp[l][k+len-1]=min(dp[l][k+len-1],dp[l][r]+cost(k+len-1-l+1,cnt,r-l+1)+b );
            }
        }
    }
}

 
int main(){
 
    cin>>n>>(s+1);
    cin>>a>>b>>c;

    power=1;
    for(int len=1;len<=n;len++){

        last.clear(); hesh=0;
        for(int t=n;t>=n-len+1;t--){
            hesh*=26; hesh+=s[t]-'a'; hesh%=mod;
        }
        power*=26; power%=mod;

        for(int t=n-len+1;t>=1;t--){

            if(!last[hesh].empty()){

                while(pt[hesh]+1<last[hesh].size() and last[hesh][pt[hesh]+1]>t+len-1){
                    pt[hesh]++;
                }

                if(pt[hesh]!=-1){
                    nxt[t][t+len-1]=last[hesh][pt[hesh]];
                }else{
                    nxt[t][t+len-1]=n+1;
                }
            }else{
                nxt[t][t+len-1]=n+1;
                pt[hesh]=-1;
            }

            last[hesh].push_back(t);

            hesh*=26; hesh+=s[t-1]-'a'; hesh%=mod;

            hesh-=(long long) ((s[t+len-1]-'a')*power)%mod;
            hesh+=mod; hesh%=mod;
        }
    }

    calc_dp();
 
    cout<<dp[1][n]<<"\n";
 
    return 0;
}

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:69:33: warning: comparison of integer expressions of different signedness: 'std::unordered_map<long long int, int>::mapped_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |                 while(pt[hesh]+1<last[hesh].size() and last[hesh][pt[hesh]+1]>t+len-1){

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