제출 #552057

#제출 시각아이디문제언어결과실행 시간메모리
552057Ronin13Copy and Paste 3 (JOI22_copypaste3)C++14
100 / 100
766 ms70736 KiB
#include<bits/stdc++.h> #define ll long long #define f first #define s second #define pii pair<int,int> #define pll pair<ll,ll> #define pb push_back #define epb emplace_back #define ull unsigned ll using namespace std; const int NMAX = 2501; const ll inf = 1e9 + 1; int dp1[NMAX][NMAX]; int adj[NMAX][NMAX]; ll dp[NMAX][NMAX]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; string s; cin >> s; ll a, b, c; cin >> a >> b >> c; for(int i = 1; i <= n; i++){ for(int j = 1; j < i; j++){ if(s[i - 1] != s[j - 1]) dp1[i][j] = 0; else dp1[i][j] = dp1[i - 1][j - 1] + 1; } } /*for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ cout << dp1[i][j] << ' '; } cout << "\n"; }*/ for(int i = 1; i <= n; i++){ int mn = 0; for(int j = i - 1; j > 0; j--){ int x = min(dp1[i][j], i - j); while(mn < x){ mn++; adj[i - mn + 1][mn] = j - mn + 1; } } } vector <vector <int> > vec(n + 1); for(int i = 1; i <= n; i++){ for(int i = 1; i <= n; i++) vec[i].clear(); for(int j = i; j >= 1; j--){ int cur = j; int len = i - j + 1; while(cur){ vec[cur].pb(len); cur = adj[cur][len]; } } ll cnt[n + 1]; for(int i = 1; i <= n; i++){ cnt[i] = 0; } ll mn = 0; dp[i][i] = a; for(int j = i; j > 0; j--){ dp[i][j] = dp[i - 1][j] + a; for(int to : vec[j]){ cnt[to]++; mn = min(mn, (c - to * a) * cnt[to] + dp[i][i - to + 1] + b); } dp[i][j] = min(dp[i][j], mn + (i - j + 1) * a); } } /*for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ cout << dp[i][j] << ' '; } cout << "\n"; }*/ cout << dp[n][1]; return 0; }
#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...