Submission #1206247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206247		mychecksedad	Copy and Paste 3 (JOI22_copypaste3)	C++20	100 / 100	555 ms	160560 KiB

copypaste3

/* Author : Mychecksdead  */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 2500+100, M = 1e5+10, K = 52, MX = 30;
const ll INF = 1e18;

int n, go[N][N];
string s;
ll a, b, c, dp[N][N], p[N], p2[N], pd[N][N];
vector<array<int, 3>> H[N];
void solve(){
  cin >> n >> s >> a >> b >> c;

  p2[0] = 1;
  p[0] = 1;
  for(int i = 1; i <= n; ++i){
    p[i] = (p[i - 1] * 37) % MOD;
    p2[i] = (p2[i - 1] * 29) % MOD1;
  }

  for(int i = 1; i <= n; ++i){
    ll h1 = 0;
    ll h2 = 0;
    for(int j = i; j <= n; ++j){
      h1 = (h1 + (s[j - 1] - 'a' + 1) * p[j - i]) % MOD;
      h2 = (h2 + (s[j - 1] - 'a' + 1) * p2[j - i]) % MOD1;
      H[j - i + 1].pb(array<int, 3>{h1, h2, i});
    }
  }

  for(int i = 1; i <= n; ++i){
    for(int j = 1; j <= n; ++j) go[i][j] = n + 1;
  }

  for(int len = 1; len <= n; ++len){
    sort(all(H[len]));
    vi v;
    v.pb(H[len][0][2]);
    for(int i = 1; i <= H[len].size(); ++i){
      if(i == H[len].size() || H[len][i][0] != H[len][i - 1][0] || H[len][i][1] != H[len][i - 1][1]){
        // process v
        go[v.back()][len] = n + 1;
        int j = v.size();
        for(int i = j - 2; i >= 0; --i){
          while(j > 0 && v[j - 1] >= v[i] + len) --j;
          if(j == v.size()) go[v[i]][len] = n + 1;
          else go[v[i]][len] = v[j];
        }
        v.clear();
      }
      v.pb(H[len][i][2]);
    }
  }

  for(int i = 1; i <= n; ++i){
    for(int j = 1; j <= n; ++j) pd[i][j] = INF;
  }

  for(int i = 1; i <= n; ++i){
    dp[i][i] = a;
  }

  for(int d = 1; d <= n; ++d){
    int len = d;

    for(int l = 1; l <= n; ++l){
      int r = go[l][len];
      int cnt = 2;
      while(r < n + 1){
        pd[l][r + len - 1] = min(pd[l][r + len - 1], dp[l][l + len - 1] + (r+len-1-l+1 - len*cnt) * a + b + c * cnt);
        ++cnt;
        r = go[r][len];
      }
    }

    for(int l = 1; l + d <= n; ++l){
      int r = l + d;
      dp[l][r] = min(dp[l+1][r], dp[l][r-1]) + a;
      dp[l][r] = min(dp[l][r], pd[l][r]);
    }
  }


  cout << dp[1][n];
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tt = 1, aa;
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  while(tt--){
    solve();
    en;
  }
  cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
  return 0;
} 

Compilation message (stderr)

copypaste3.cpp: In function 'void solve()':
copypaste3.cpp:37:37: warning: narrowing conversion of 'h1' from 'long long int' to 'int' [-Wnarrowing]
   37 |       H[j - i + 1].pb(array<int, 3>{h1, h2, i});
      |                                     ^~
copypaste3.cpp:37:41: warning: narrowing conversion of 'h2' from 'long long int' to 'int' [-Wnarrowing]
   37 |       H[j - i + 1].pb(array<int, 3>{h1, h2, 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