Submission #635883

#	Time	Username	Problem	Language	Result	Execution time	Memory
635883		Mahdi	Copy and Paste 3 (JOI22_copypaste3)	C++17	30 / 100	588 ms	27004 KiB

copypaste3

#include<bits/stdc++.h>
#pragma GCC optimize ("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=2505, M=1e9+7;
int n, h[N], t[N], tt[N][N];
ll A, B, C, dp[N][N], pd[N][N], o[N];
string s;

void opr(const int &j, vector<int>&v){
    v.push_back(n);
    int k=v.size()-1;
    for(int i=v.size()-2;i>=0;--i){
        while(k>0 && v[i]+j<v[k-1])
            --k;
        t[v[i]]=v[k];
    }
}

int main(){
    cin>>n>>s>>A>>B>>C;
    if(n>200){
        for(int i=1;i<=n;++i){
            o[i]=A*i;
            for(int j=1;j<i;++j)
                o[i]=min(o[i], o[j]+B+C*(i/j)+(i%j)*A);
        }
        cout<<o[n]<<'\n';
        return 0;
    }
    for(int i=0;i<=n;++i){
        fill(dp[i], dp[i]+n+1, 1e18);
    }
    for(int i=0;i<=n;++i){
        for(int j=i;j<=n;++j)
            dp[i][j]=A*(j-i);
    }
    for(int j=0;j<n;++j){
        for(int i=0;i<=n;++i){
            for(int k=i;k<=n;++k)
                pd[i][k]=(k-i)*A;
        }
        for(int i=0;i<n-j;++i)
            h[i]=(1LL*h[i]*37+s[i+j]-'a')%M;
        vector<pii>v;
        vector<int>w;
        for(int i=0;i<n-j;++i)
            v.push_back({h[i], i});
        sort(all(v));
        w.push_back(v[0].S);
        for(int i=1;i<n-j;++i){
            if(v[i].F==v[i-1].F)
                w.push_back(v[i].S);
            else{
                opr(j, w);
                w.clear();
                w.push_back(v[i].S);
            }
        }
        opr(j, w);
        memset(tt, 0, sizeof(tt));
        for(int i=n-j-1;i>=0;--i){
            for(int k=i+j+1;k<=n;++k){
                tt[i][k]=1;
                if(t[i]<k)
                    tt[i][k]+=tt[t[i]][k];
                dp[i][k]=min(dp[i][k], dp[i][i+j+1]+B+C*tt[i][k]+(k-i-tt[i][k]*(j+1))*A);
            }
        }
        for(int i=0;i<=n;++i){
            for(int k=i+1;k<=n;++k)
                dp[i][k]=min(dp[i][k], dp[i+1][k]+A);
        }
    }
    cout<<dp[0][n]<<'\n';
}

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