Submission #445488

#TimeUsernameProblemLanguageResultExecution timeMemory
445488lohachoVim (BOI13_vim)C++14
100 / 100
93 ms80408 KiB
#include <bits/stdc++.h> #define int long long #define umi(x, y) (x = min(x, y)) #define uma(x, y) (x = max(x, y)) using namespace std; int dp[70004][12][12], ns[70004]; signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; string in; cin >> in; string s; vector<int> must; int cnt = 0, ans = 0; for(auto&i:in){ if(i == 'e') ++cnt; else{ s += i; must.push_back(!!cnt); ans += cnt * 2; cnt = 0; } } n = (int)s.size(); for(int i = 0; i < 70004; ++i) for(int j = 0; j < 12; ++j) for(int k = 0; k < 12; ++k) dp[i][j][k] = ns[i] = (int)1e9; for(int i = 1; i <= 11; ++i) dp[1][i][0] = 0; for(int i = 1; i < n; ++i){ for(int j = 1; j <= 11; ++j){ for(int k = 0; k <= 11; ++k){ umi(dp[i][j][k], ns[i]); if(!k){ if(s[i] - 'a' + 1 == j){ umi(ns[i + 1], dp[i][j][k] + 2); } else{ if(!must[i]) umi(dp[i + 1][j][0], dp[i][j][0]); for(int x = 1; x <= 11; ++x){ umi(dp[i + 1][j][x], dp[i][j][0] + 1); } } } else{ if(s[i] - 'a' + 1 == j && j == k){ umi(ns[i + 1], dp[i][j][k] + 4); } else if(s[i] - 'a' + 1 == j){ umi(dp[i + 1][k][0], dp[i][j][k] + 2); for(int x = 1; x <= 11; ++x){ umi(dp[i + 1][x][k], dp[i][j][k] + 3); } } else if(s[i] - 'a' + 1 == k){ for(int x = 1; x <= 11; ++x){ umi(dp[i + 1][j][x], dp[i][j][k] + 3); } } else{ umi(dp[i + 1][j][k], dp[i][j][k] + 1); } } } } } int ans2 = (int)1e9; for(int i = n - 1; i >= 0; --i){ umi(ans2, dp[i][s[i] - 'a' + 1][0] + 2); umi(ans2, dp[i][s[i] - 'a' + 1][11] + 2); if(must[i]) break; } cout << ans + ans2; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...