| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 757416 |
2023-06-13T07:16:30 Z |
The_Samurai |
Vim (BOI13_vim) |
C++17 |
|
2000 ms |
524288 KB |
#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);
};
auto dist = [&](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 ans;
};
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(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(*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
vim.cpp: In function 'int main()':
vim.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | 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 time |
Memory |
Grader output |
| 1 |
Correct |
712 ms |
596 KB |
Output is correct |
| 2 |
Incorrect |
156 ms |
436 KB |
Output isn't correct |
| 3 |
Incorrect |
116 ms |
412 KB |
Output isn't correct |
| 4 |
Correct |
198 ms |
424 KB |
Output is correct |
| 5 |
Correct |
249 ms |
340 KB |
Output is correct |
| 6 |
Incorrect |
615 ms |
536 KB |
Output isn't correct |
| 7 |
Incorrect |
396 ms |
484 KB |
Output isn't correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
212 KB |
Output is correct |
| 13 |
Correct |
743 ms |
612 KB |
Output is correct |
| 14 |
Incorrect |
147 ms |
428 KB |
Output isn't correct |
| 15 |
Incorrect |
109 ms |
412 KB |
Output isn't correct |
| 16 |
Incorrect |
145 ms |
440 KB |
Output isn't correct |
| 17 |
Correct |
179 ms |
340 KB |
Output is correct |
| 18 |
Incorrect |
159 ms |
412 KB |
Output isn't correct |
| 19 |
Incorrect |
150 ms |
420 KB |
Output isn't correct |
| 20 |
Correct |
165 ms |
340 KB |
Output is correct |
| 21 |
Correct |
191 ms |
420 KB |
Output is correct |
| 22 |
Correct |
263 ms |
460 KB |
Output is correct |
| 23 |
Incorrect |
59 ms |
340 KB |
Output isn't correct |
| 24 |
Incorrect |
51 ms |
340 KB |
Output isn't correct |
| 25 |
Incorrect |
62 ms |
364 KB |
Output isn't correct |
| 26 |
Correct |
92 ms |
340 KB |
Output is correct |
| 27 |
Correct |
357 ms |
468 KB |
Output is correct |
| 28 |
Incorrect |
586 ms |
468 KB |
Output isn't correct |
| 29 |
Incorrect |
374 ms |
480 KB |
Output isn't correct |
| 30 |
Incorrect |
84 ms |
340 KB |
Output isn't correct |
| 31 |
Incorrect |
60 ms |
356 KB |
Output isn't correct |
| 32 |
Incorrect |
84 ms |
368 KB |
Output isn't correct |
| 33 |
Incorrect |
108 ms |
340 KB |
Output isn't correct |
| 34 |
Correct |
282 ms |
452 KB |
Output is correct |
| 35 |
Incorrect |
456 ms |
492 KB |
Output isn't correct |
| 36 |
Incorrect |
392 ms |
480 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2079 ms |
37660 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2073 ms |
22148 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2089 ms |
8788 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2077 ms |
37716 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2087 ms |
19028 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2080 ms |
7764 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2081 ms |
27756 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2066 ms |
26196 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2041 ms |
22100 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2081 ms |
19452 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
194 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Runtime error |
197 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Runtime error |
195 ms |
524288 KB |
Execution killed with signal 9 |
| 4 |
Runtime error |
195 ms |
524288 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
192 ms |
524288 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
207 ms |
524288 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
198 ms |
524288 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
189 ms |
524288 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
196 ms |
524288 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
196 ms |
524288 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
222 ms |
524288 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
193 ms |
524288 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
210 ms |
524288 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
195 ms |
524288 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
197 ms |
524288 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
203 ms |
524288 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
188 ms |
524288 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
184 ms |
524288 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
211 ms |
524288 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
243 ms |
524288 KB |
Execution killed with signal 9 |
