| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 757410 |
2023-06-13T07:11:41 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;
if (now == 0) {
cout << x;
}
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:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | 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 |
823 ms |
612 KB |
Output is correct |
| 2 |
Incorrect |
168 ms |
488 KB |
Output isn't correct |
| 3 |
Incorrect |
131 ms |
412 KB |
Output isn't correct |
| 4 |
Correct |
291 ms |
424 KB |
Output is correct |
| 5 |
Correct |
293 ms |
448 KB |
Output is correct |
| 6 |
Incorrect |
701 ms |
544 KB |
Output isn't correct |
| 7 |
Incorrect |
450 ms |
488 KB |
Output isn't correct |
| 8 |
Correct |
1 ms |
320 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
914 ms |
612 KB |
Output is correct |
| 14 |
Incorrect |
173 ms |
424 KB |
Output isn't correct |
| 15 |
Incorrect |
117 ms |
412 KB |
Output isn't correct |
| 16 |
Incorrect |
182 ms |
428 KB |
Output isn't correct |
| 17 |
Correct |
169 ms |
416 KB |
Output is correct |
| 18 |
Incorrect |
182 ms |
340 KB |
Output isn't correct |
| 19 |
Incorrect |
148 ms |
428 KB |
Output isn't correct |
| 20 |
Correct |
170 ms |
460 KB |
Output is correct |
| 21 |
Correct |
220 ms |
340 KB |
Output is correct |
| 22 |
Correct |
277 ms |
444 KB |
Output is correct |
| 23 |
Incorrect |
49 ms |
316 KB |
Output isn't correct |
| 24 |
Incorrect |
53 ms |
340 KB |
Output isn't correct |
| 25 |
Incorrect |
70 ms |
340 KB |
Output isn't correct |
| 26 |
Correct |
107 ms |
396 KB |
Output is correct |
| 27 |
Correct |
352 ms |
464 KB |
Output is correct |
| 28 |
Incorrect |
644 ms |
588 KB |
Output isn't correct |
| 29 |
Incorrect |
403 ms |
488 KB |
Output isn't correct |
| 30 |
Incorrect |
87 ms |
384 KB |
Output isn't correct |
| 31 |
Incorrect |
62 ms |
376 KB |
Output isn't correct |
| 32 |
Incorrect |
88 ms |
340 KB |
Output isn't correct |
| 33 |
Incorrect |
135 ms |
384 KB |
Output isn't correct |
| 34 |
Correct |
314 ms |
444 KB |
Output is correct |
| 35 |
Incorrect |
464 ms |
496 KB |
Output isn't correct |
| 36 |
Incorrect |
403 ms |
492 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2058 ms |
37716 KB |
Time limit exceeded |
| 2 |
Execution timed out |
2063 ms |
22100 KB |
Time limit exceeded |
| 3 |
Execution timed out |
2065 ms |
8788 KB |
Time limit exceeded |
| 4 |
Execution timed out |
2070 ms |
37716 KB |
Time limit exceeded |
| 5 |
Execution timed out |
2073 ms |
18992 KB |
Time limit exceeded |
| 6 |
Execution timed out |
2073 ms |
7764 KB |
Time limit exceeded |
| 7 |
Execution timed out |
2061 ms |
27828 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2060 ms |
26068 KB |
Time limit exceeded |
| 9 |
Execution timed out |
2049 ms |
22100 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2076 ms |
19396 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
213 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Runtime error |
210 ms |
524288 KB |
Execution killed with signal 9 |
| 3 |
Runtime error |
229 ms |
524288 KB |
Execution killed with signal 9 |
| 4 |
Runtime error |
236 ms |
524288 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
203 ms |
524288 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
195 ms |
524288 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
209 ms |
524288 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
209 ms |
524288 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
209 ms |
524288 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
197 ms |
524288 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
202 ms |
524288 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
231 ms |
524288 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
207 ms |
524288 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
223 ms |
524288 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
205 ms |
524288 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
204 ms |
524288 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
227 ms |
524288 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
200 ms |
524288 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
209 ms |
524288 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
197 ms |
524288 KB |
Execution killed with signal 9 |
