Submission #757424

#TimeUsernameProblemLanguageResultExecution timeMemory
757424The_SamuraiVim (BOI13_vim)C++17
50 / 100
2080 ms524288 KiB
#include "bits/stdc++.h" using namespace std; int INF = 1e9; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); clock_t startTime = clock(); int n; string s; cin >> n >> s; vector<vector<int>> pos(150); vector<int> not_e; for (int i = 0; i < n; i++) { pos[s[i]].emplace_back(i); if (s[i] != 'e') { not_e.emplace_back(i); } } if (pos['e'].empty()) { cout << 0; return 0; } auto cnt = [&](int l, int r, char x) { return upper_bound(pos[x].begin(), pos[x].end(), r) - lower_bound(pos[x].begin(), pos[x].end(), l); }; vector<vector<int>> dist(n, vector<int>(n, INF)); auto dist_calc = [&](int l, int r) { int ans = INF; for (char x = 'a'; x <= 'z'; x++) { if (x == 'e' or pos[x].empty() or pos[x].back() < r) continue; int first = *lower_bound(pos[x].begin(), pos[x].end(), r); int now = cnt(l + 1, first, x) * 2; now += first - r; ans = min(ans, now); } return min(ans, dist[l][r]); }; for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { dist[i][j] = dist_calc(i, j); } } for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { if (i <= k and k <= j) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } } vector<vector<int>> dp(pos['e'].size(), vector<int>(pos['e'].size(), INF)); for (int i = 0; i < dp.size(); i++) { // birinchi i ta 'e' ni o'chirish for (int j = 0; j <= i; j++) { // birinchi i ta 'e' ni o'chirib, j-'e' da to'xtash if (j == 0) { int now = dist_calc(0, pos['e'][i]); // orasida hammasi bilan yurib chiqish now += pos['e'][i] - pos['e'][0]; // 'e' larni o'chirish now += i + 1; dp[i][j] = now; continue; // bu qismi to'g'ri } for (int k = 0; k < j; k++) { int now = dp[j - 1][k] + dist_calc(*lower_bound(not_e.begin(), not_e.end(), pos['e'][k]), pos['e'][i]); now += pos['e'][i] - pos['e'][j]; now += i - j + 1; dp[i][j] = min(dp[i][j], now); } } } // i = 2, j = 2, k = 0 cout << *min_element(dp.back().begin(), dp.back().end()); #ifdef sunnitov cerr << "\nTime: " << (int)((double)(clock() - startTime) / CLOCKS_PER_SEC * 1000); #endif } /* chefeddiefedjeffeachbigagedegghehad - 0 chefeddiefedjeffeachbigagedegghehad - 0 */

Compilation message (stderr)

vim.cpp: In function 'int main()':
vim.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < dp.size(); i++) {
      |                     ~~^~~~~~~~~~~
vim.cpp:9:13: warning: unused variable 'startTime' [-Wunused-variable]
    9 |     clock_t startTime = clock();
      |             ^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...