Submission #1215741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215741		noyancanturk	Copy and Paste 3 (JOI22_copypaste3)	C++20	100 / 100	2185 ms	362760 KiB

copypaste3

#include<bits/stdc++.h>
using namespace std;

#define int int64_t

const int lim=2510;

int n;
string s;
int dp[lim][lim];

int pws[lim],hsh[lim][lim];

const int mod=(1ll<<61)-1;

int sum(int i,int j){
  if(i+j<mod)return i+j;
  return i+j-mod;
}
int sub(int i,int j){
  if(j<=i)return i-j;
  return i-j+mod;
}
int mul(int i,int j){
  return __int128_t(i)*j%mod;
}

unordered_map<int,vector<int>>mp[lim];

signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  cin>>n;
  cin>>s;
  int a,b,c;
  cin>>a>>b>>c;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      dp[i][j]=LLONG_MAX;
    }
  }
  for(int l=0;l<n;l++){
    hsh[l][l]=s[l];
    for(int r=l+1;r<n;r++){
      hsh[l][r]=sum(s[r],mul(hsh[l][r-1],37));
      mp[r-l][hsh[l][r]].push_back(r);
    }
  }
  for(int l=n-1;0<=l;l--){
    dp[l][l]=a;
    int cc=1;
    for(int r=l+1;r<n;r++){
      if(s[l]==s[r])cc++;
      dp[l][r]=a+b+cc*c + a*(r-l+1-cc);
    }
    for(int r=l+1;r<n;r++){
      dp[l][r]=min(dp[l][r],min(dp[l+1][r],dp[l][r-1])+a);
      int len=r-l+1;
      auto&m=mp[r-l][hsh[l][r]];
      auto p=upper_bound(m.begin(),m.end(),r+len-1);
      int cur=1;
      while(p!=m.end()){
        cur++;
        dp[l][*p]=min(dp[l][*p],dp[l][r]+b+cur*c+(*p-l+1-cur*len)*a);
        p=upper_bound(m.begin(),m.end(),*p+len-1);
      }
    }
  }
  cout<<dp[0][n-1]<<'\n';
}

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