Submission #922681

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

copypaste3

#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)

const int N=2510;
int f[N][N], add, cut, paste, n;
int g[N][N];
string s;

void precalc(){
   for (int t=1; t<=n; ++t){
      map<string, int> mp;
      for (int r=t; r<=n; ++r){
         string s1=s.substr(r-t+1, t);
         g[r][t]=mp.count(s1)?mp[s1]:-1;
         if (r-t+1>=t){
            string s2=s.substr(r-t+1-t+1, t);
            mp[s2]=r-t+1;
         }
      }
   }
}

int count(int l, int r, int t){
   if (r-l+1<t) return 0;
   int pos=g[r][t];
   return count(l, pos, t)+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=l; t<=r; ++t){
      int cnt=count(l, r, r-t+1);
      if (cnt!=1) 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(){
   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