Submission #945179

#	Time	Username	Problem	Language	Result	Execution time	Memory
945179		vjudge1	Copy and Paste 3 (JOI22_copypaste3)	C++17	62 / 100	349 ms	49748 KiB

copypaste3

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#warning That's the baby, that's not my baby

typedef long long ll;

const int NMAX = 2500;
const int mod = 1e9 + 123;
const int P = 31;

int hsh[NMAX + 1], nxt[NMAX + 1];
std::vector<int> v[NMAX + 1];
ll dp[NMAX + 1][NMAX + 1];

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n;
  std::cin >> n;

  std::string s;
  std::cin >> s;
  s = '#' + s;

  int A, B, C;
  std::cin >> A >> B >> C;

  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++) {
      dp[i][j] = 1e18;
    }
    for(int j = i; j <= n; j++) {
      dp[i][j] = (ll) (j - i + 1) * A;
    }
  }
  for(int len = 1; len <= n; len++) {
    std::vector<std::pair<int, int>> x;
    for(int i = 1; i <= n - len + 1; i++) {
      hsh[i] = ((ll) hsh[i] * 31 + (s[i + len - 1] - 'a' + 1)) % mod;
      dp[i][i + len - 1] = std::min({dp[i][i + len - 1], dp[i + 1][i + len - 1] + A, dp[i][i + len - 2] + A});
      x.push_back({hsh[i], i});
    }
    std::sort(x.begin(), x.end());
    int cur = 0;
    for(int i = 0; i < x.size(); i++) {
      if(!i || x[i].first != x[i - 1].first) {
        cur++;
      }
      v[cur].push_back(x[i].second);
    }
    for(int i = 1; i <= cur; i++) {
      for(int j = (int)v[i].size() - 1; j >= 0; j--) {
        int l = j + 1, r = v[i].size();
        while(l < r) {
          int mid = (l + r) / 2;
          if(v[i][mid] >= v[i][j] + len) {
            r = mid;
          } else {
            l = mid + 1;
          }
        }
        nxt[j] = r;
      }
      for(int j = 0; j < (int) v[i].size(); j++) {
        int cur = j, cnt = 0;
        while(cur < (int) v[i].size()) {
          int l = v[i][j], r = v[i][cur] + len - 1;
          dp[l][r] = std::min(dp[l][r], (ll)(cnt + 1) * C + (ll)(r - l + 1 - (cnt + 1) * len) * A + B + dp[l][l + len - 1]);
          cnt++;
          int x = nxt[cur];
          if(x == (int) v[i].size()) {
            break;
          }
          cur = x;
        }
      }
      v[i].clear();
    }
  }

  std::cout << dp[1][n];

  return 0;
}

Compilation message (stderr)

copypaste3.cpp:6:2: warning: #warning That's the baby, that's not my baby [-Wcpp]
    6 | #warning That's the baby, that's not my baby
      |  ^~~~~~~
copypaste3.cpp: In function 'int main()':
copypaste3.cpp:49:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i = 0; i < x.size(); i++) {
      |                    ~~^~~~~~~~~~

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