Submission #1307104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307104		reginox	Copy and Paste 3 (JOI22_copypaste3)	C++20	100 / 100	1306 ms	167568 KiB

copypaste3

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
const int N = 2503;
const ll mod = 1e9+7, base = 311, mod2 = 998244353;
int n; ll a, b, c;
ll h[N], pw[N] = {1};
ll h2[N], pw2[N] = {1};
string s;
map<pi, int> rc[N];
int nx[N][N];

pi get(int l, int r){
  return make_pair((h[r] - (h[l-1] * pw[r-l+1] % mod) + mod) % mod, (h2[r] - (h2[l-1] * pw2[r-l+1] % mod2) + mod2) % mod2);
}

void init(){
  for(int i = 1; i <= n; i++){
    h[i] = (h[i-1] * base + s[i]) % mod;
    h2[i] = (h2[i-1] * base + s[i]) % mod2;
    pw[i] = (pw[i-1] * base) % mod;
    pw2[i] = (pw2[i-1] * base) % mod2;
  }
  for(int i = n; i >= 1; i--){
    for(int j = i; j <= n; j++){
      pi hc = get(i, j);
      if(rc[j-i].count(hc)) nx[i][j] = rc[j-i][hc];
      else nx[i][j] = n+1;
    }
    for(int j = i; j <= n; j++){
      pi hc = get(j, j+j-i);
      if(j+j-i > n) break;
      rc[j-i][hc] = j;
    }
  }
}

ll dp[N][N];

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> s >> a >> b >> c;
  s = ' ' + s;
  init();
  memset(dp, 0x3f, sizeof(dp));
  for(int i = 1; i <= n; i++) dp[i][i+1] = a+b;
  for(int len = 1; len < n; len++){
    for(int i = 1; i + len - 1 <= n; i++){
      int j = i + len;
      if(i > 1){
        dp[i-1][j] = min(dp[i-1][j], dp[i][j] + a);
      }
      if(j <= n){
        dp[i][j+1] = min(dp[i][j+1], dp[i][j] + a);
      }
      ll cur = i, cnt = 1;
      while(nx[cur][cur + len-1] <= n){
        if(nx[cur][cur+len-1] == 0) break;
        cur = nx[cur][cur+len-1];
        cnt++;
        dp[i][cur + len] = min(dp[i][cur + len], dp[i][j] + c * cnt + b + a * (cur + len - i - 1ll * cnt * len));
      }
    }
  }
  // for(int i = 1; i <= n; i++){
  //   for(int j = 1; i + j - 1 <= n; j++){
  //     cout << i << " " << i+j << " ";
  //     cout << (dp[i][i+j] >= 1e18? -1:dp[i][i+j]) << " ";
  //   cout << "\n";
  //   }
  // }
  cout << dp[1][n+1] - b;
  return 0;
}

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