Submission #1013979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013979		ReLice	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	443 ms	128448 KiB

copypaste3

#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>*/
template<class S,class T>
bool chmin(S &a,const T &b) {
	return a>b?(a=b)==b:false;
}
template<class S,class T>
bool chmax(S &a,const T &b) {
	return a<b?(a=b)==b:false;
}
//void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=1e18;
const ll mod=998244353;
const ll mod2=1e9+11;
const ll N=3e3+7;
const ld eps=1e-9;
ll dp[N][N];
pair<ll,ll> h[N][N];
ll nxt[N][N];
void solve(){
    ll i,j;
    ll n,a,b,c;
    str s;
    cin>>n>>s;
    cin>>a>>b>>c;
    for(i=0;i<n;i++){
        //dp[i][i]=a;
        h[i][i].fr=s[i]-'a'+1;
        h[i][i].sc=s[i]-'a'+1;
        for(j=i+1;j<n;j++){
            h[i][j].fr=h[i][j-1].fr*29+(s[j]-'a'+1);
            h[i][j].fr%=mod;
            h[i][j].sc=h[i][j-1].sc*37+(s[j]-'a'+1);
            h[i][j].sc%=mod2;
            //dp[i][j]+=a*(j-i+1);
        }
    }
    for(ll len=1;len<=n;len++){
        map<pair<ll,ll>,ll> mp;
        for(i=n-len;i>=0;i--){
            if(i+len*2-1<n)mp[h[i+len][i+len*2-1]]=i+len;
            if(mp.count(h[i][i+len-1])) nxt[i][i+len-1]=mp[h[i][i+len-1]];
            else nxt[i][i+len-1]=-1;
            //if(nxt[i][i+len-1]>=0)cout<<i<<' '<<i+len-1<<' '<<nxt[i][i+len-1]<<endl;
        }
        for(i=0;i<=n-len;i++){
            if(len>1){
                chmin(dp[i][i+len-1],dp[i][i+len-2]);
                chmin(dp[i][i+len-1],dp[i+1][i+len-1]);
            }
            ll cnt=1;
            ll id=i;
            while(true){
                cnt++;
                if(nxt[id][id+len-1]==-1)break;
                id=nxt[id][id+len-1];
                chmin(dp[i][id+len-1],dp[i][i+len-1]+b+c*cnt-a*len*(cnt-1));
            }
        }
    }
    cout<<a*n+dp[0][n-1]<<endl;
}
signed main(){
    start();
    ll t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}
/*
a<b<c<d
a a
b b

a a
a a



*/

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