Submission #922694

#	Time	Username	Problem	Language	Result	Execution time	Memory
922694		huutuan	Copy and Paste 3 (JOI22_copypaste3)	C++14	57 / 100	3035 ms	438452 KiB

copypaste3

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define isz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)

pair<int, int> mod={(int)1e9+7, (int)1e9+9};
const int base=311;

struct Hash{
   pair<int, int> value;
   Hash (int x=0){
      value={x%mod.first, x%mod.second};
   }
   Hash (int x, int y){
      value={x, y};
   }
   Hash operator-(){
      return Hash((mod.first-value.first)%mod.first, 
                  (mod.second-value.second)%mod.second);
   }
   Hash operator+(Hash b){
      return Hash((value.first+b.value.first)%mod.first, 
                  (value.second+b.value.second)%mod.second);
   }
   Hash operator*(Hash b){
      return Hash(value.first*b.value.first%mod.first, 
                  value.second*b.value.second%mod.second);
   }
   bool operator<(Hash b) const {
      return value<b.value;
   }
   bool operator==(Hash b) const {
      return value==b.value;
   }
};

const int N=2510, LG=12;
int f[N][N], add, cut, paste, n;
int g[N][N];
int jump[LG][N][N];
Hash pf[N];
Hash pw[N];
string s;

Hash get(int l, int r){
   return pf[r]+(-pf[l-1])*pw[r-l+1];
}

void precalc(){
   pw[0]=1;
   for (int i=1; i<=n; ++i){
      pw[i]=pw[i-1]*base;
   }
   for (int i=1; i<=n; ++i){
      pf[i]=pf[i-1]*base+s[i];
   }
   for (int t=1; t<=n; ++t){
      map<Hash, int> mp;
      for (int r=t; r<=n; ++r){
         Hash h1=get(r-t+1, r);
         g[r][t]=mp.count(h1)?mp[h1]:0;
         if (r-t+1>=t){
            Hash h2=get(r-t+1-t+1, r-t+1);
            mp[h2]=r-t+1;
         }
      }
   }
   for (int i=0; i<=n; ++i) for (int j=0; j<LG; ++j) jump[j][0][i]=0;
   for (int i=1; i<=n; ++i){
      for (int j=1; j<=i; ++j) jump[0][i][j]=g[i][j];
   }
   for (int k=1; k<LG; ++k){
      for (int i=1; i<=n; ++i){
         for (int j=1; j<=i; ++j) jump[k][i][j]=jump[k-1][jump[k-1][i][j]][j];
      }
   }
}

int count(int l, int r, int t){
   int ans=0;
   for (int i=LG-1; i>=0; --i){
      if (jump[i][r][t]>=l+t-1){
         ans+=1<<i;
         r=jump[i][r][t];
      }
   }
   return ans+1;
}

int dp(int l, int r){
   if (l>r) return 0;
   if (f[l][r]!=-1) return f[l][r];
   int res=dp(l, r-1)+add;
   for (int t=r; t>=l; --t){
      int cnt=count(l, r, r-t+1);
      if (cnt==1) break;
      int ll=max(l, r-(r-l+1)/cnt+1), rr=t-1;
      while (ll<=rr){
         int mid=(ll+rr)>>1;
         if (count(l, r, r-mid+1)==cnt) rr=mid-1;
         else ll=mid+1;
      }
      t=ll;
      res=min(res, dp(t, r)+cut+cnt*paste+add*(r-l+1-cnt*(r-t+1)));
   }
   return f[l][r]=res;
}

void solve(){
   memset(f, -1, sizeof f);
   cin >> n >> s;
   s=" "+s;
   precalc();
   cin >> add >> cut >> paste;
   cout << dp(1, n);
}

int32_t main(){
   #ifdef sus
   freopen("cf.inp", "r", stdin);
   #endif
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int ntests=1;
   // cin >> ntests;
   for (int i=1; i<=ntests; ++i) solve();
   return 0;
}

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