Submission #958450

#TimeUsernameProblemLanguageResultExecution timeMemory
958450MarwenElarbiCopy and Paste 3 (JOI22_copypaste3)C++17
100 / 100
1338 ms98652 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define vi vector<int> #define ve vector #define ll long long #define vl vector<ll> #define vll vector<pair<ll,ll>> #define onbit __builtin_popcount #define ii pair<int,int> #define vvi vector<vi> #define vii vector<ii> #define gii greater<ii> #define pb push_back #define mp make_pair #define fi first #define se second #define INF 1e18 #define eps 1e-7 #define eps1 1e-2 #define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define MAX_A 1e5+5 using namespace std; using namespace __gnu_pbds; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll MOD = (1LL << 61) - 1; const int nax = 1e5+5; const int MAX_VAL = 1e6+1; double PI=3.14159265359; int arx[8]={1,0,0,-1,-1,-1, 1, 1}; int ary[8]={0,1,-1, 0, 1,-1,-1, 1}; void setIO(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } const int d=41; int main(){ optimise; /*#ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif*/ //setIO("dec"); ll n,a,b,c; string s; cin>>n>>s>>a>>b>>c; s="#"+s; long long hash[n+1][n+1]; long long dp[n+1][n+1]; memset(hash,0,sizeof hash); for (int i = 1; i <= n; ++i) { for (int j = i; j <= n ; ++j) { hash[i][j]=(hash[i][j-1]*26+s[j]-'a')%MOD; } for (int j = 0; j <= n; ++j) { dp[i][j]=1e18; } dp[i][i]=a; } for (ll h = 1; h <= n; ++h) { vector<pair<ll,ll>> cand; for (int i = 1; i <= n-h+1; ++i) { dp[i][i+h-1]=min(dp[i][i+h-1],min(dp[i][i+h-2],dp[i+1][i+h-1])+a); cand.pb({hash[i][i+h-1],i}); } sort(cand.begin(),cand.end()); for(auto u:cand){ ll x=1; ll i=u.se; while(true){ int pos=lower_bound(cand.begin(),cand.end(),mp(u.fi,i+h))-cand.begin(); if(pos<cand.size()&&cand[pos].fi==u.fi){ i=cand[pos].se; x++; //cout <<h<<" "<<i<<endl; dp[u.se][i+h-1]=min(dp[u.se][i+h-1],dp[u.se][u.se+h-1] + b + c*x + a*(i+h-u.se-x*h)); }else break; } } } cout <<dp[1][n]<<endl; }

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:80:23: 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]
   80 |                 if(pos<cand.size()&&cand[pos].fi==u.fi){
      |                    ~~~^~~~~~~~~~~~
copypaste3.cpp: In function 'void setIO(std::string)':
copypaste3.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
copypaste3.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...