Submission #1038707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038707		juicy	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	353 ms	123312 KiB

copypaste3

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2505;

int n, A, B, C;
int sa[N], lcp[N], nxt[N][N];
long long dp[N][N], g[N][N];
string s;

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> s >> A >> B >> C;
  s = '&' + s;
  iota(sa + 1, sa + n + 1, 1);
  sort(sa + 1, sa + n + 1, [&](int i, int j) {
    return s.substr(i) < s.substr(j);
  });
  for (int i = 1; i < n; ++i) {
    int u = sa[i], v = sa[i + 1];
    while (u + lcp[i] <= n && v + lcp[i] <= n && s[u + lcp[i]] == s[v + lcp[i]]) {
      ++lcp[i];
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ) {
      int k = j;
      while (lcp[k] >= i) {
        ++k;
      }
      vector<int> cands;
      while (j <= k) {
        cands.push_back(sa[j++]);
      }
      sort(cands.rbegin(), cands.rend());
      k = -1;
      for (int u : cands) {
        while (k + 1 < cands.size() && cands[k + 1] - u >= i) {
          ++k;
        }
        nxt[u][i] = k == -1 ? k : cands[k];
      }
    }
  }
  memset(dp, 0x3f, sizeof(dp));
  memset(g, 0x3f, sizeof(g));
  for (int i = 1; i <= n; ++i) {
    dp[i][i] = A;
  }
  for (int l = 1; l <= n; ++l) {
    for (int i = 1, j = l; j <= n; ++i, ++j) {
      auto &cur = dp[i][j];
      cur = min(cur, g[i][j]);
      dp[i][j + 1] = min(dp[i][j + 1], cur + A);
      int st = i, cnt = 0, sz = 0;
      while (1) {
        int ed = st + l - 1;
        ++cnt;
        sz += l;
        g[i][ed] = min(g[i][ed], (long long) (ed - i + 1 - sz) * A + B + (long long) C * cnt + cur);
        if (nxt[st][l] == -1) {
          break;
        } 
        st = nxt[st][l];
      }
      g[i - 1][j] = min(g[i - 1][j], g[i][j] + A);
      g[i][j + 1] = min(g[i][j + 1], g[i][j] + A);
    }
  }
  cout << dp[1][n];
  return 0;
}

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         while (k + 1 < cands.size() && cands[k + 1] - u >= i) {
      |                ~~~~~~^~~~~~~~~~~~~~

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