Submission #544847

#	Time	Username	Problem	Language	Result	Execution time	Memory
544847		MarcoMeijer	Copy and Paste 3 (JOI22_copypaste3)	C++14	100 / 100	2145 ms	233660 KiB

copypaste3

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

typedef long long ll;

const int MX = 3001;

int n;
ll a, b, c;
string s;
map<string, vector<int>> idx;
ll dp[MX][MX];

vector<string> suffixes;
ll lenShare[MX];
ll rsuf[MX];

int main() {
  cin >> n >> s >> a >> b >> c;

  // sort suffixes
  for (int i=0; i<n; i++) {
    string t = s.substr(i, n-i);
    suffixes.push_back(t);
  }
  sort(suffixes.begin(), suffixes.end());
  for (int i=0; i<n; i++) rsuf[n-suffixes[i].size()] = i;

  // calculate the length the suffixes share
  for (int i=0; i<n; i++) {
    lenShare[i] = 0;
    if (i == 0) continue;
    int mx = min(suffixes[i-1].size(), suffixes[i].size());
    while (lenShare[i] < mx && suffixes[i-1][lenShare[i]] == suffixes[i][lenShare[i]])
      lenShare[i]++;
  }

  vector<pair<int,vector<int>>> v;
  for (int i=0; i<n; i++) {
    for (int l=lenShare[rsuf[i]] + 1; l<=n-i; l++) {
      vector<int> V;
      V.push_back(i);
      for (int x=rsuf[i]+1; x<n; x++) {
        int share = lenShare[x];
        if (share < l)
          break;
        V.push_back(n-suffixes[x].size());
      }
      sort(V.begin(), V.end());
      v.push_back({l, V});
    }
  }

  ll lastL = 1;
  sort(v.begin(), v.end());
  for (auto& p : v) {
    ll l = p.first;
    while (lastL < l) {
      for (int i=0; i<n-l+1; i++) {
        dp[i][i+l-1] = min(dp[i][i+l-1], dp[i+1][i+l-1]);
        dp[i][i+l-1] = min(dp[i][i+l-1], dp[i][i+l-2]);
      }
      lastL++;
    }

    vector<int> V = p.second;
    ll baseCost = dp[V[0]][V[0]+l-1] + a*l + b;
    ll profit = c - a*l;
    if (profit > 0) continue;
    for (int i=0; i<V.size(); i++) {
      ll lst = -1e9;
      ll cnt = 0;
      for (int j=i; j<V.size(); j++) {
        if (lst + l > V[j])
          continue;
        lst = V[j];
        cnt++;
        dp[V[i]][lst+l-1] = min(dp[V[i]][lst+l-1], baseCost + profit*cnt);
      }
    }
  }

  cout << dp[0][n-1] + a * n << endl;
}

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:70:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int i=0; i<V.size(); i++) {
      |                   ~^~~~~~~~~
copypaste3.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |       for (int j=i; j<V.size(); j++) {
      |                     ~^~~~~~~~~

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