Submission #972715

#TimeUsernameProblemLanguageResultExecution timeMemory
972715happy_nodeCopy and Paste 3 (JOI22_copypaste3)C++17
100 / 100
412 ms162728 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MX=2505; int N, A, B, C; string s; ll dp[MX][MX]; const ll P=1e9+409, mod=2e9-223; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ll hsh[MX][MX], pw[MX], key[MX]; int nxt[MX][MX]; vector<pair<ll,ll>> v[MX]; int main() { cin.tie(0); ios_base::sync_with_stdio(0); for(int i=0;i<MX;i++) for(int j=i;j<MX;j++) dp[i][j]=2e18; pw[0]=1; for(int i=1;i<MX;i++) pw[i]=pw[i-1]*P%mod; cin>>N; cin>>s; cin>>A>>B>>C; s='#'+s; for(int c=0;c<26;c++) key[c]=rng()%mod; for(int l=1;l<=N;l++) { for(int r=l;r<=N;r++) { int p=r-l+1; hsh[l][r]=hsh[l][r-1]+pw[p]*(key[s[r]-'a'])%mod; hsh[l][r]%=mod; v[p].push_back({hsh[l][r],l}); } } for(int i=1;i<=N;i++) { sort(v[i].begin(),v[i].end()); int k=0; for(int j=0;j<v[i].size();j++) { if(k<j) k++; while(k<v[i].size() && v[i][k+1].first==v[i][k].first && v[i][k].second<v[i][j].second+i) { k++; } if(k>=v[i].size()) { nxt[v[i][j].second][v[i][j].second+i-1]= -1; continue; } if(v[i][k].second<v[i][j].second+i) { nxt[v[i][j].second][v[i][j].second+i-1]= -1; continue; } nxt[v[i][j].second][v[i][j].second+i-1]=v[i][k].second; } } for(int l=N;l>0;l--) { for(int r=l;r<=N;r++) { dp[l][r]=min(dp[l][r],dp[l][r-1]+A); ll k=nxt[l][r], p=r-l+1, z=1; while(k!=-1) { z++; ll len=k+p-1-l+1; dp[l][k+p-1]=min(dp[l][k+p-1],dp[l][r]+z*C+B+(len-p*z)*A); k=nxt[k][k+p-1]; } dp[l-1][r]=min(dp[l-1][r],dp[l][r]+A); } } cout<<dp[1][N]<<'\n'; }

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:53:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int j=0;j<v[i].size();j++) {
      |               ~^~~~~~~~~~~~
copypaste3.cpp:56:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |    while(k<v[i].size() && v[i][k+1].first==v[i][k].first
      |          ~^~~~~~~~~~~~
copypaste3.cpp:60:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |    if(k>=v[i].size()) {
      |       ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...