Submission #724679

#	Time	Username	Problem	Language	Result	Execution time	Memory
724679		MohammadAghil	Copy and Paste 3 (JOI22_copypaste3)	C++17	62 / 100	435 ms	33988 KiB

copypaste3

#include <bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define all(x) begin(x), end(x)
#define sz(x) (int)size(x)
#define pb push_back
#define ff first
#define ss second
typedef long long ll;
typedef pair<int, int> pp;

void dbg(){
     cerr << endl;
}
template<typename H, typename... T> void dbg(H h, T... t){
     cerr << h << ", ";
     dbg(t...);
}

void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     #ifndef ONLINE_JUDGE
          // freopen("inp.txt", "r", stdin);
          // freopen("out.txt", "w", stdout);
          #define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">: ", dbg(__VA_ARGS__)
     #else
          #define er(...) 0
     #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll mod = 998244353, maxn = 25e2 + 5, lg = 21, inf = ll(1e18) + 5, p = 9973;

ll dp[maxn][maxn];
ll pw[maxn], hsh[maxn];

void buildHsh(string s){
     hsh[0] = s[0];
     rep(i,1,sz(s)){
          hsh[i] = (hsh[i-1]*p%mod + s[i])%mod;
     }
     pw[0] = 1;
     rep(i,1,sz(s)) pw[i] = pw[i-1]*p%mod;
}

int get(int l, int r){
     return (hsh[r] - (l? hsh[l-1]*pw[r-l+1]%mod: 0) + mod)%mod;
}

int main(){ IOS();
     int n; cin >> n;
     string s; cin >> s;
     ll A, C, P; cin >> A >> C >> P;
     rep(i,0,n){
          rep(j,i,n) dp[i][j] = inf;
     }
     buildHsh(s);
     rep(l,1,n+1){
          map<int, int> mp;
          vector<int> prv(n, -1);
          rep(i,0,n-l+1){
               int j = i + l - 1;
               if(i < j) dp[i][j] = min({dp[i][j], dp[i+1][j] + A, dp[i][j-1] + A});
               else dp[i][j] = A;
               if(i >= l) mp[get(i-l, i-1)] = i-l;
               int cr = get(i, j);
               if(mp.count(cr)) prv[i] = mp[cr];
               int x = prv[i];
               int cnt = 2;
               while(x + 1){
                    dp[x][j] = min(dp[x][j], P*cnt + dp[i][j] + C + (j - x + 1 - l*cnt)*A);
                    x = prv[x];
                    cnt++;
               }
          }    
     }
     cout << dp[0][n-1] << '\n';
     return 0;
}

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