| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 491815 |
2021-12-04T14:50:58 Z |
Victor |
Vim (BOI13_vim) |
C++17 |
|
2000 ms |
200344 KB |
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
const int INF = 1'000'000'007;
vi lets[130];
int n, cnt = 0, memo[5001][5001];
string str;
int dp(int pos, int taken) {
if (taken == cnt) return 0;
int &ans = memo[pos][taken];
if (ans != -1) return memo[pos][taken];
ans = INF;
if (lets['e'][taken] <= pos) {
int nxt_taken = upper_bound(all(lets['e']), pos) - lets['e'].begin();
ans = (pos - lets['e'][taken]) + dp(lets['e'][taken], nxt_taken);
}
rep(i, 'a', 'z' + 1) {
if (i == 'e') continue;
vi &vec = lets[i];
auto it = upper_bound(all(vec), pos);
if (it!=vec.end()) ans = min(ans, 2 + dp(*it, taken));
}
return ans;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
memset(memo, -1, sizeof(memo));
cin >> n >> str;
rep(i, 0, n) lets[str[i]].pb(i);
cnt = sz(lets['e']);
cout << dp(0, 0) + cnt<< endl;
return 0;
}
Compilation message
vim.cpp: In function 'int main()':
vim.cpp:66:29: warning: array subscript has type 'char' [-Wchar-subscripts]
66 | rep(i, 0, n) lets[str[i]].pb(i);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
98120 KB |
Output is correct |
| 2 |
Incorrect |
44 ms |
98192 KB |
Output isn't correct |
| 3 |
Incorrect |
39 ms |
98124 KB |
Output isn't correct |
| 4 |
Incorrect |
55 ms |
98092 KB |
Output isn't correct |
| 5 |
Correct |
46 ms |
98196 KB |
Output is correct |
| 6 |
Incorrect |
57 ms |
98192 KB |
Output isn't correct |
| 7 |
Incorrect |
56 ms |
98116 KB |
Output isn't correct |
| 8 |
Correct |
36 ms |
98252 KB |
Output is correct |
| 9 |
Correct |
35 ms |
98092 KB |
Output is correct |
| 10 |
Incorrect |
36 ms |
98116 KB |
Output isn't correct |
| 11 |
Correct |
36 ms |
98148 KB |
Output is correct |
| 12 |
Correct |
43 ms |
98112 KB |
Output is correct |
| 13 |
Correct |
57 ms |
98184 KB |
Output is correct |
| 14 |
Incorrect |
52 ms |
98124 KB |
Output isn't correct |
| 15 |
Incorrect |
44 ms |
98116 KB |
Output isn't correct |
| 16 |
Incorrect |
48 ms |
98124 KB |
Output isn't correct |
| 17 |
Incorrect |
49 ms |
98200 KB |
Output isn't correct |
| 18 |
Incorrect |
45 ms |
98204 KB |
Output isn't correct |
| 19 |
Correct |
48 ms |
98212 KB |
Output is correct |
| 20 |
Correct |
44 ms |
98208 KB |
Output is correct |
| 21 |
Incorrect |
54 ms |
98092 KB |
Output isn't correct |
| 22 |
Correct |
49 ms |
98196 KB |
Output is correct |
| 23 |
Incorrect |
45 ms |
98140 KB |
Output isn't correct |
| 24 |
Incorrect |
46 ms |
98192 KB |
Output isn't correct |
| 25 |
Incorrect |
45 ms |
98124 KB |
Output isn't correct |
| 26 |
Incorrect |
48 ms |
98284 KB |
Output isn't correct |
| 27 |
Incorrect |
55 ms |
98116 KB |
Output isn't correct |
| 28 |
Incorrect |
59 ms |
98252 KB |
Output isn't correct |
| 29 |
Incorrect |
52 ms |
98180 KB |
Output isn't correct |
| 30 |
Incorrect |
45 ms |
98196 KB |
Output isn't correct |
| 31 |
Incorrect |
44 ms |
98164 KB |
Output isn't correct |
| 32 |
Incorrect |
49 ms |
98108 KB |
Output isn't correct |
| 33 |
Incorrect |
50 ms |
98196 KB |
Output isn't correct |
| 34 |
Incorrect |
51 ms |
98112 KB |
Output isn't correct |
| 35 |
Incorrect |
52 ms |
98124 KB |
Output isn't correct |
| 36 |
Incorrect |
54 ms |
98188 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1081 ms |
98344 KB |
Output isn't correct |
| 2 |
Execution timed out |
2081 ms |
98252 KB |
Time limit exceeded |
| 3 |
Incorrect |
499 ms |
98216 KB |
Output isn't correct |
| 4 |
Incorrect |
1059 ms |
98340 KB |
Output isn't correct |
| 5 |
Execution timed out |
2084 ms |
98252 KB |
Time limit exceeded |
| 6 |
Incorrect |
1596 ms |
98500 KB |
Output isn't correct |
| 7 |
Incorrect |
1343 ms |
98340 KB |
Output isn't correct |
| 8 |
Incorrect |
1365 ms |
98356 KB |
Output isn't correct |
| 9 |
Execution timed out |
2083 ms |
98332 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2083 ms |
98336 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
112 ms |
199756 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
115 ms |
200120 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
115 ms |
200068 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
124 ms |
200232 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
112 ms |
199936 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
118 ms |
199828 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
116 ms |
200052 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
115 ms |
199996 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
120 ms |
200004 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
115 ms |
199796 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
117 ms |
200176 KB |
Execution killed with signal 11 |
| 12 |
Runtime error |
117 ms |
199932 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
113 ms |
200344 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
129 ms |
200320 KB |
Execution killed with signal 11 |
| 15 |
Runtime error |
115 ms |
200112 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
111 ms |
200028 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
116 ms |
199696 KB |
Execution killed with signal 11 |
| 18 |
Runtime error |
111 ms |
200132 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
130 ms |
200132 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
117 ms |
199868 KB |
Execution killed with signal 11 |
