Submission #634709

#	Time	Username	Problem	Language	Result	Execution time	Memory
634709		alvingogo	Copy and Paste 3 (JOI22_copypaste3)	C++14	100 / 100	1868 ms	220888 KiB

copypaste3

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

signed main(){
    AquA;
    string s;
    int n,a,b,c;
    const int bs=37,mod=1e9+7;
    cin >> n >> s >> a >> b >> c;
    vector<vector<int> > g(n,vector<int>(n));
    vector<int> p;
    for(int i=0;i<n;i++){
        int k=0;
        for(int j=i;j<n;j++){
            k*=bs;
            k+=s[j];
            k%=mod;
            g[i][j]=k;
            p.push_back(g[i][j]);
        }
    }
    sort(p.begin(),p.end());
    p.erase(unique(p.begin(),p.end()),p.end());
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            g[i][j]=lower_bound(p.begin(),p.end(),g[i][j])-p.begin();
        }
    }
    vector<vector<int> > from(n,vector<int>(n,-1));
    vector<int> m(n*n,-1);
    for(int l=1;l<=n;l++){
        for(int j=0;j+l-1<n;j++){
            from[j][j+l-1]=m[g[j][j+l-1]];
            if(j-l+1>=0){
                m[g[j-l+1][j]]=j-l+1;
            }
        }
        for(int j=0;j+l-1<n;j++){
            if(j-l+1>=0){
                m[g[j-l+1][j]]=-1;
            }
        }
    }
    vector<vector<int> > zzz(n,vector<int>(n,1e18));
    for(int r=0;r<n;r++){
        for(int l=r;l>=0;l--){
            if(l==r){
                zzz[l][r]=a;
            }
            else{
                zzz[l][r]=min(zzz[l][r],min(zzz[l+1][r]+a,zzz[l][r-1]+a));
            }
            int j=from[l][r],t=2;
            for(;j>=0;j=from[j][j+r-l]){
                zzz[j][r]=min(zzz[j][r],zzz[l][r]+c*t+b+a*(r-j+1-(r-l+1)*t));
                t++;
            }
            //cout << l << " " << r << " " << zzz[l][r] << "\n";
        }
    }
    cout << zzz[0][n-1] << "\n";
    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