Submission #998244

#	Time	Username	Problem	Language	Result	Execution time	Memory
998244		abczz	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	408 ms	181540 KiB

copypaste3

#include <iostream>
#include <vector>
#include <array>
#include <map>
#define ll long long

using namespace std;

string S;
const ll M = 1e9 + 7, M2 = 1e9 + 11;
map <array<ll, 2>, ll> mp;
array <ll, 2> X[2510][2510];
ll n, a, b, c, s, s2, base = 37, base2 = 41, p, p2, dp[2510][2500], nx[2510][2510];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> S >> a >> b >> c;
  for (ll i=0; i<n; ++i) {
    s = s2 = 0, p = p2 = 1;
    for (ll j=i; j<n; ++j) {
      (s += (S[j]-'a'+1) * p % M) %= M;
      (p *= base) %= M;
      (s2 += (S[j]-'a'+1) * p2 % M2) %= M2;
      (p2 *= base2) %= M2;
      X[i][j] = {s, s2};
    }
  }
  for (ll len=0; len<n; ++len) {
    mp.clear();
    for (ll i=n-len-1; i>=0; --i) {
      if (i+2*len+1 < n) {
        mp[X[i+len+1][i+2*len+1]] = i+len+1;
      }
      if (mp.count(X[i][i+len])) nx[i][i+len] = mp[X[i][i+len]];
      else nx[i][i+len] = -1;
    }
    for (ll i=0; i+len<n; ++i) {
      if (len) {
        dp[i][i+len] = min(dp[i][i+len], min(dp[i][i+len-1], dp[i+1][i+len]));
      }
      s = 0;
      ll j = i;
      while (true) {
        ll k = nx[j][j+len];
        ++s;
        if (k == -1) break;
        dp[i][k+len] = min(dp[i][k+len], dp[i][i+len] + b + (s+1) * c - (s * (len+1) * a));
        j = k;
      }
    }
  }
  cout << a*n + dp[0][n-1] << '\n';
}

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