| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 491811 |
2021-12-04T14:42:43 Z |
Victor |
Vim (BOI13_vim) |
C++17 |
|
2000 ms |
200388 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 num_e = upper_bound(all(lets['e']), pos) - lets['e'].begin() - taken;
ans = num_e + (pos - lets['e'][taken]) + dp(lets['e'][taken], num_e + taken);
}
rep(i, 'a', 'z' + 1) {
if (i == 'e') continue;
vi &vec = lets[i];
int idx = upper_bound(all(vec), pos) - vec.begin();
if (idx != sz(vec)) ans = min(ans, 2 + dp(vec[idx], 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) << endl;
return 0;
}
Compilation message
vim.cpp: In function 'int dp(int, int)':
vim.cpp:53:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | if (idx != sz(vec)) ans = min(ans, 2 + dp(vec[idx], taken));
| ^
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 |
98124 KB |
Output is correct |
| 2 |
Incorrect |
44 ms |
98096 KB |
Output isn't correct |
| 3 |
Incorrect |
40 ms |
98120 KB |
Output isn't correct |
| 4 |
Incorrect |
47 ms |
98152 KB |
Output isn't correct |
| 5 |
Correct |
48 ms |
98172 KB |
Output is correct |
| 6 |
Incorrect |
54 ms |
98168 KB |
Output isn't correct |
| 7 |
Incorrect |
51 ms |
98128 KB |
Output isn't correct |
| 8 |
Correct |
37 ms |
98188 KB |
Output is correct |
| 9 |
Correct |
36 ms |
98124 KB |
Output is correct |
| 10 |
Incorrect |
38 ms |
98116 KB |
Output isn't correct |
| 11 |
Correct |
37 ms |
98124 KB |
Output is correct |
| 12 |
Correct |
35 ms |
98068 KB |
Output is correct |
| 13 |
Correct |
49 ms |
98116 KB |
Output is correct |
| 14 |
Incorrect |
46 ms |
98212 KB |
Output isn't correct |
| 15 |
Incorrect |
41 ms |
98124 KB |
Output isn't correct |
| 16 |
Incorrect |
44 ms |
98088 KB |
Output isn't correct |
| 17 |
Incorrect |
49 ms |
98180 KB |
Output isn't correct |
| 18 |
Incorrect |
45 ms |
98124 KB |
Output isn't correct |
| 19 |
Correct |
43 ms |
98228 KB |
Output is correct |
| 20 |
Correct |
44 ms |
98128 KB |
Output is correct |
| 21 |
Incorrect |
46 ms |
98116 KB |
Output isn't correct |
| 22 |
Correct |
48 ms |
98116 KB |
Output is correct |
| 23 |
Incorrect |
44 ms |
98124 KB |
Output isn't correct |
| 24 |
Incorrect |
44 ms |
98112 KB |
Output isn't correct |
| 25 |
Incorrect |
45 ms |
98116 KB |
Output isn't correct |
| 26 |
Incorrect |
47 ms |
98100 KB |
Output isn't correct |
| 27 |
Incorrect |
51 ms |
98088 KB |
Output isn't correct |
| 28 |
Incorrect |
56 ms |
98076 KB |
Output isn't correct |
| 29 |
Incorrect |
52 ms |
98188 KB |
Output isn't correct |
| 30 |
Incorrect |
45 ms |
98180 KB |
Output isn't correct |
| 31 |
Incorrect |
47 ms |
98160 KB |
Output isn't correct |
| 32 |
Incorrect |
46 ms |
98124 KB |
Output isn't correct |
| 33 |
Incorrect |
46 ms |
98172 KB |
Output isn't correct |
| 34 |
Incorrect |
48 ms |
98116 KB |
Output isn't correct |
| 35 |
Incorrect |
49 ms |
98116 KB |
Output isn't correct |
| 36 |
Incorrect |
52 ms |
98280 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1056 ms |
98344 KB |
Output isn't correct |
| 2 |
Execution timed out |
2081 ms |
98244 KB |
Time limit exceeded |
| 3 |
Incorrect |
438 ms |
98332 KB |
Output isn't correct |
| 4 |
Incorrect |
1040 ms |
98348 KB |
Output isn't correct |
| 5 |
Execution timed out |
2081 ms |
98244 KB |
Time limit exceeded |
| 6 |
Incorrect |
1591 ms |
98396 KB |
Output isn't correct |
| 7 |
Incorrect |
1347 ms |
98416 KB |
Output isn't correct |
| 8 |
Incorrect |
1343 ms |
98272 KB |
Output isn't correct |
| 9 |
Execution timed out |
2087 ms |
98244 KB |
Time limit exceeded |
| 10 |
Execution timed out |
2075 ms |
98296 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
117 ms |
199848 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
119 ms |
200132 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
114 ms |
200228 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
117 ms |
200296 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
112 ms |
200088 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
119 ms |
199904 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
115 ms |
200256 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
112 ms |
200004 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
114 ms |
200128 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
113 ms |
199864 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
111 ms |
200284 KB |
Execution killed with signal 11 |
| 12 |
Runtime error |
113 ms |
200052 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
122 ms |
200388 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
112 ms |
200348 KB |
Execution killed with signal 11 |
| 15 |
Runtime error |
116 ms |
200320 KB |
Execution killed with signal 11 |
| 16 |
Runtime error |
112 ms |
200132 KB |
Execution killed with signal 11 |
| 17 |
Runtime error |
111 ms |
199832 KB |
Execution killed with signal 11 |
| 18 |
Runtime error |
121 ms |
200136 KB |
Execution killed with signal 11 |
| 19 |
Runtime error |
113 ms |
200132 KB |
Execution killed with signal 11 |
| 20 |
Runtime error |
113 ms |
199948 KB |
Execution killed with signal 11 |
