Submission #256384

#TimeUsernameProblemLanguageResultExecution timeMemory
256384SaboonVim (BOI13_vim)C++14
13.89 / 100
43 ms1536 KiB
#include <bits/stdc++.h> using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef long long ll; const int maxn = 500 + 10; int nex[maxn][12]; int dp[maxn][maxn]; int pd[maxn]; int main(){ ios_base::sync_with_stdio(false); int n; string s; cin >> n >> s; for (int i = 0; i < 10; i++){ int last = -1; for (int j = n-1; j >= 0; j--){ if (last == -1) nex[j][i] = j; else nex[j][i] = last; if ((int)(s[j] - 'a') == i and s[j] != 'e') last = j; } } vector<int> e; for (int i = 0; i < n; i++) if (s[i] == 'e') e.push_back(i); if (e.empty()) return cout << 0 << endl, 0; int m = e.size(); memset(dp, 63, sizeof dp); dp[0][0] = 0; for (int j = 0; j <= m; j++){ memset(pd, 63, sizeof pd); if (j > 0) pd[e[j-1]] = 0; else pd[0] = 0; for (int i = 0; i < n; i++) for (int c = 0; c < 10; c++) if (nex[i][c] != i) pd[nex[i][c]] = min(pd[nex[i][c]], pd[i] + 2); for (int i = j; i <= m; i++){ int it = i; int idx = (j == 0 ? 0 : e[j-1]); for (; idx < n; idx ++){ if (s[idx] == 'e') continue; while (it < m and e[it] < idx) it ++; if (it == i) continue; dp[it][i+1] = min(dp[it][i+1], dp[i][j] + pd[idx] + (idx-e[i]) + (it-i)); } } } int answer = 4*n; for (int i = 1; i <= m; i++) answer = min(answer, dp[m][i]); cout << answer << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...