Submission #448239

#TimeUsernameProblemLanguageResultExecution timeMemory
448239prvocisloVim (BOI13_vim)C++17
100 / 100
116 ms55048 KiB
#include <iostream> #include <vector> #include <string> using namespace std; const int abc = 11, inf = 1e9 + 5; void upd(int& a, const int& b) { a = min(a, b); } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; string s; cin >> s; int cnte = 0; vector<int> t; vector<bool> u; for (int i = 0; i < n; i++) { if (s[i] == 'e') cnte++; else { t.push_back(s[i] - 'a'); u.push_back(i && s[i - 1] == 'e'); } //if (s[i] == 'e') cout << 2; //else cout << (int)u.back(); } //cout << endl; t.push_back(abc - 1), u.push_back(false); int m = t.size(); vector<vector<int> > p(m, vector<int>(abc, inf)); vector<vector<vector<int> > > q(m, vector<vector<int> >(abc, vector<int>(abc, inf))); p[0][t[0]] = q[0][t[0]][t[0]] = 0; for (int a = 0; a < m - 1; a++) { for (int c = 0; c < abc; c++) { if (!u[a] && c != t[a]) upd(p[a + 1][c], p[a][c]); upd(p[a + 1][c], p[a][t[a]] + 2); if (c != t[a]) upd(p[a + 1][c], q[a][t[a]][c]); upd(p[a + 1][c], q[a][t[a]][t[a]] + 2); for (int d = 0; d < abc; d++) { if (c != t[a]) upd(q[a + 1][c][d], p[a][c] + 3); upd(q[a + 1][c][d], p[a][t[a]] + 5); if (c != t[a] && d != t[a]) upd(q[a + 1][c][d], q[a][c][d] + 1); if (c != t[a]) upd(q[a + 1][c][d], q[a][c][t[a]] + 3); if (d != t[a]) upd(q[a + 1][c][d], q[a][t[a]][d] + 3); upd(q[a + 1][c][d], q[a][t[a]][t[a]] + 5); } } } cout << p[m - 1][abc - 1] - 2 + cnte * 2 << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...