Submission #883503

#	Time	Username	Problem	Language	Result	Execution time	Memory
883503		MilosMilutinovic	Copy and Paste 3 (JOI22_copypaste3)	C++14	100 / 100	628 ms	49756 KiB

copypaste3

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

const int BASE = 77777;
const int md1 = 1e9 + 7;
const int md2 = 1e9 + 9;

int ckadd1(int a, int b) {
  return a + b < md1 ? a + b : a + b - md1;
}

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

int ckmul1(int a, int b) {
  return a * 1LL * b % md1;
}

int ckadd2(int a, int b) {
  return a + b < md2 ? a + b : a + b - md2;
}

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

int ckmul2(int a, int b) {
  return a * 1LL * b % md2;
}

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

int qpow2(int x, int k) {
  int ret = 1;
  while (k) {
    if (k & 1) {
      ret = ckmul2(ret, x);
    }
    x = ckmul2(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> pw1(n);
  pw1[0] = 1;
  for (int i = 1; i < n; i++) {
    pw1[i] = ckmul1(pw1[i - 1], BASE);
  }
  vector<int> dv1(n);
  dv1[n - 1] = qpow1(pw1[n - 1], md1 - 2);
  for (int i = n - 2; i >= 0; i--) {
    dv1[i] = ckmul1(dv1[i + 1], BASE);
  }
  vector<int> pref1(n);
  for (int i = 0; i < n; i++) {
    if (i > 0) {
      pref1[i] = pref1[i - 1];
    }
    pref1[i] = ckadd1(pref1[i], ckmul1(pw1[i], s[i] - 'a'));
  }
  vector<int> pw2(n);
  pw2[0] = 1;
  for (int i = 1; i < n; i++) {
    pw2[i] = ckmul2(pw2[i - 1], BASE);
  }
  vector<int> dv2(n);
  dv2[n - 1] = qpow2(pw2[n - 1], md2 - 2);
  for (int i = n - 2; i >= 0; i--) {
    dv2[i] = ckmul2(dv2[i + 1], BASE);
  }
  vector<int> pref2(n);
  for (int i = 0; i < n; i++) {
    if (i > 0) {
      pref2[i] = pref2[i - 1];
    }
    pref2[i] = ckadd2(pref2[i], ckmul2(pw2[i], s[i] - 'a'));
  }
  auto Get1 = [&](int L, int R) {
    int ret = pref1[R];
    if (L > 0) {
      ret = cksub1(ret, pref1[L - 1]);
    }
    return ckmul1(ret, dv1[L]); 
  };
  auto Get2 = [&](int L, int R) {
    int ret = pref2[R];
    if (L > 0) {
      ret = cksub2(ret, pref2[L - 1]);
    }
    return ckmul2(ret, dv2[L]); 
  };
  auto Get = [&](int L, int R) {
    return make_pair(Get1(L, R), Get2(L, R));
  };
  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<pair<int, 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;
      }
      pair<int, 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: 38 / 38