Submission #44245

#TimeUsernameProblemLanguageResultExecution timeMemory
44245neutron_byteVim (BOI13_vim)C++17
4.17 / 100
2082 ms1276 KiB
#include <bits/stdc++.h> #define INF 10000000 using namespace std; int main() { int n; cin >> n; string s; cin >> s; int dp[n]; dp[n - 1] = 0; for (int i = n - 2; i >= 0; --i) { if (s[i] == 'e') { dp[i] = 1 + dp[i + 1]; continue; } dp[i] = INF; // check all possibilities to jump for (char c = 'a'; c <= 'j'; ++c) { if (c == 'e') continue; // find next occurrence int pos = i + 1; while (pos < n && s[pos] != c) { ++pos; } if (pos >= n) { continue; } // jump from i to pos int firstE = -1; int cntE = 0; for (int j = pos - 1; j > i; --j) { if (s[j] == 'e') { ++cntE; firstE = j; } } bool onlyE = true; for (int j = pos - 1; j >= firstE; --j) { if (s[j] != 'e') { onlyE = false; break; } } int afterE = 0; for (int j = pos + 1; j < n; ++j) { if (s[j] == 'e') ++afterE; } if (afterE > 0) { for (char d = 'a'; d <= 'j'; ++d) { if (d == 'e') continue; bool betweenE = false; int nextOcc = -1; for (int j = i + 1; j < n; ++j) { if (s[j] == d) { nextOcc = j; break; } } if (nextOcc == -1 || nextOcc < pos) continue; for (int j = pos + 1; j <= nextOcc; ++j) { if (s[j] == 'e') { betweenE = true; break; } } if (!betweenE) { if (cntE > 0) dp[i] = min(dp[i], (onlyE ? 2 : 4) + pos - firstE + cntE + dp[nextOcc]); else dp[i] = min(dp[i], 2 + dp[nextOcc]); } } } else { if (cntE > 0) dp[i] = min(dp[i], 2 + pos - firstE + cntE); else dp[i] = 0; } } /* if (cntE > 0) { if (afterE > 0) { dp[i] = min(dp[i], (onlyE ? 2 : 4) + pos - firstE + cntE + dp[pos]); } else { dp[i] = min(dp[i], 2 + pos - firstE + cntE); } } else { if (afterE > 0) { dp[i] = min(dp[i], 2 + dp[pos]); } else { dp[i] = 0; } } } */ } /* for (int i = 0; i < n; ++i) { cout << "dp[" << i << "] = " << dp[i] << endl; } */ cout << dp[0] << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...