Submission #998176

#	Time	Username	Problem	Language	Result	Execution time	Memory
998176		abczz	Copy and Paste 3 (JOI22_copypaste3)	C++17	62 / 100	231 ms	131928 KiB

copypaste3

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

using namespace std;

string S;
const ll M = 1e9 + 9;
unordered_map <ll, ll> mp;
ll n, a, b, c, s, base = 37, p, X[2500][2500], dp[2500][2500], nx[2500][2500];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> S >> a >> b >> c;
  for (int i=0; i<n; ++i) {
    s = 0, p = 1;
    for (int j=i; j<n; ++j) {
      (s += (S[j]-'a'+1) * p % M) %= M;
      (p *= base) %= M;
      X[i][j] = s;
    }
  }
  for (int len=0; len<n; ++len) {
    mp.clear();
    for (int 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 (int 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;
      int j = i;
      while (true) {
        int 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: 0 / 38