제출 #883481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
883481		MilosMilutinovic	Copy and Paste 3 (JOI22_copypaste3)	C++14	62 / 100	582 ms	49860 KiB

copypaste3

#include <bits/stdc++.h>
 
using namespace std;

const int BASE = 77777;
const int md = 1e9 + 7;

int ckadd(int a, int b) {
  return a + b < md ? a + b : a + b - md;
}

int cksub(int a, int b) {
    return a >= b ? a - b : a - b + md;
}

int ckmul(int a, int b) {
  return a * 1LL * b % md;
}

int qpow(int x, int k) {
  int ret = 1;
  while (k) {
    if (k & 1) {
      ret = ckmul(ret, x);
    }
    x = ckmul(x, x);
    k >>= 1;
  }
  return ret;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  string s;
  cin >> s;
  int a, b, c;
  cin >> a >> b >> c;
  vector<int> pw(n);
  pw[0] = 1;
  for (int i = 1; i < n; i++) {
    pw[i] = ckmul(pw[i - 1], BASE);
  }
  vector<int> dv(n);
  dv[n - 1] = qpow(pw[n - 1], md - 2);
  for (int i = n - 2; i >= 0; i--) {
    dv[i] = ckmul(dv[i + 1], BASE);
  }
  vector<int> pref(n);
  for (int i = 0; i < n; i++) {
    if (i > 0) {
      pref[i] = pref[i - 1];
    }
    pref[i] = ckadd(pref[i], ckmul(pw[i], s[i] - 'a'));
  }
  auto Get = [&](int L, int R) {
    int ret = pref[R];
    if (L > 0) {
      ret = cksub(ret, pref[L - 1]);
    }
    return ckmul(ret, dv[L]); 
  };
  const long long inf = (long long) 1e18;
  vector<vector<long long>> dp(n, vector<long long>(n, inf));
  for (int len = 0; len < n; len++) {
    vector<int> to(n, -1);
    map<int, int> mp;
    for (int l = n - len - 1; l >= 0; l--) {
      int r = l + len;
      if (r + 1 + len < n) {
        mp[Get(r + 1, r + 1 + len)] = r + 1;
      }
      int h = Get(l, r);
      if (mp[h] != 0) {
        to[l] = mp[h];
      }
      if (l == r) {
        dp[l][r] = a;
      }
      if (l < r) {
        dp[l][r] = min(dp[l][r], min(dp[l + 1][r], dp[l][r - 1]) + a);
      }
      {
        int x = l;
        int cnt = 1;
        while (to[x] != -1) {
          x = to[x];
          cnt += 1;
          dp[l][x + len] = min(dp[l][x + len], dp[l][r] + b + c * 1LL * cnt + a * 1LL * ((x + len - l + 1) - cnt * (len + 1)));
        }
      }
    }
  }
  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