Submission #941821

#	Time	Username	Problem	Language	Result	Execution time	Memory
941821		vjudge1	Copy and Paste 3 (JOI22_copypaste3)	C++17	20 / 100	3052 ms	800 KiB

copypaste3

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

using ll = long long;
#define int ll

#define endl '\n'
#define pb push_back
using pi = array<int, 2>;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

/*
x = lungimea
y = aparitii

cost_nor = A * len * ap
cost_cut = A * len + B + C * ap

A * len * ap - A * len - B - C * ap > 0

A*x*y - A*x - C*y - B > 0
y*(A*x-C) > A * x + B
y > (A * x + B) / (A * x - C)x
*/

const int INF = 1e9, BASE = 29, MOD = 1e9 + 7, N = 205;
int binpow(int a, int b) {
  int res = 1;
  while (b) {
    if (b & 1) res = res * a % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return res;
}
int modinv(int n) {
  return binpow(n, MOD - 2);
}

int p[N], minv[N];
void precalc() {
  p[0] = 1;
  for (int i = 1; i < N; ++i) {
    p[i] = p[i - 1] * BASE % MOD;
    minv[i] = modinv(p[i]);
  }
}

int n, A, B, C;
string s;

int dp[N][N];
int calc(int l, int r) {
  if (r < l) return 0;
  if (dp[l][r] != -1) return dp[l][r];
  
  int m = r - l + 1;
  dp[l][r] = A * m;
  for (int len = max(0LL, (ll)sqrt(m) - 5); len <= m; ++len) {
    map<int, vector<int>> ap{};
    
    int hash = 0;
    for (int i = 0; i < len; ++i) {
      hash = (hash + p[i] * s[l + i] % MOD) % MOD;
    }
    ap[hash].pb(l);
    
    for (int i = len; i < m; ++i) {
      int j = i - len;
      hash = (hash + MOD - s[l + j]) % MOD;
      hash = hash * minv[1] % MOD;
      hash = (hash + p[len - 1] * s[l + i] % MOD) % MOD;
      
      int st = l + i - len + 1;
      if (!ap[hash].size() || ap[hash].back() + len <= l + st) ap[hash].pb(st);
    }
    
    for (auto [h, idx] : ap) {
      int curr = calc(idx[0], idx[0] + len - 1) + B + idx.size() * C;
      
      curr += max(0LL, A * (idx[0] - l));
      for (int i = 1; i < (int)idx.size(); ++i) curr += max(0LL, A * (idx[i] - (idx[i - 1] + len)));
      curr += max(0LL, A * (r - (idx.back() + len) + 1));
            
      dp[l][r] = min(dp[l][r], curr);
    }
  }
  
  return dp[l][r];
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  precalc();
  
  cin >> n >> s >> A >> B >> C;
  
  bool all_a = true;
  for (int i = 0; i < n; ++i) all_a &= (s[i] == 'a');
  if (all_a) {
    vector<int> dp(n + 1, INF);
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
      dp[i] = dp[i - 1] + A;
      for (int len = 1; len < i; ++len) {
        dp[i] = min(dp[i], dp[len] + B + C * (i / len) + A * (i % len));
      }
    }
    cout << dp[n];
    return 0;
  }
  
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) dp[i][j] = -1;
  }
  
  cout << calc(0, n - 1) << endl;
}

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