Submission #1206240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206240		mychecksedad	Copy and Paste 3 (JOI22_copypaste3)	C++20	62 / 100	3111 ms	485616 KiB

copypaste3

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 2500+100, M = 1e5+10, K = 52, MX = 30;
const ll INF = 1e18;

int n, go[N][N], pi[N];
string s;
ll a, b, c, dp[N][N], h[N][N], p[N], pd[N][N];
map<int, vector<int>> H[N];
void solve(){
  cin >> n >> s >> a >> b >> c;

  p[0] = 1;
  for(int i = 1; i <= n; ++i){
    p[i] = (p[i - 1] * 37) % MOD;
  }

  for(int i = 1; i <= n; ++i){
    h[i][i - 1] = 0;
    for(int j = i; j <= n; ++j){
      h[i][j] = (h[i][j - 1] + (s[j - 1] - 'a' + 1) * p[j - i]) % MOD;
      H[j - i + 1][h[i][j]].pb(i);
    }
  }

  for(int i = 1; i <= n; ++i){
    for(int j = 1; j <= n; ++j) go[i][j] = n + 1;
  }

  for(int len = 1; len <= n; ++len){
    for(auto [ha, v]: H[len]){
      go[v.back()][len] = n + 1;
      int j = v.size();
      for(int i = j - 2; i >= 0; --i){
        while(j > 0 && v[j - 1] >= v[i] + len) --j;
        if(j == v.size()) go[v[i]][len] = n + 1;
        else go[v[i]][len] = v[j];
      }
    }
  }
  // for(int i = 1; i <= n; ++i){
  //   for(int len = 1; len <= n; ++len){
  //     cerr << i << ' ' << len << ' ' << go[i][len] << '\n';
  //   }
  //   en;
  // }

  for(int i = 1; i <= n; ++i){
    for(int j = 1; j <= n; ++j) pd[i][j] = INF;
  }

  for(int i = 1; i <= n; ++i){
    dp[i][i] = a;
  }

  for(int d = 1; d <= n; ++d){
    int len = d;

    for(int l = 1; l <= n; ++l){
      int r = go[l][len];
      int cnt = 2;
      while(r < n + 1){
        pd[l][r + len - 1] = min(pd[l][r + len - 1], dp[l][l + len - 1] + (r+len-1-l+1 - len*cnt) * a + b + c * cnt);
        ++cnt;
        r = go[r][len];
      }
    }

    for(int l = 1; l + d <= n; ++l){
      int r = l + d;
      dp[l][r] = min(dp[l+1][r], dp[l][r-1]) + a;
      dp[l][r] = min(dp[l][r], pd[l][r]);
    }
  }


  cout << dp[1][n];
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\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