oj.uz

Submission #491816

# Submission time Handle Problem Language Result Execution time Memory
491816 2021-12-04T15:08:52 Z Victor Vim (BOI13_vim) C++17
60 / 100
 1673 ms 200912 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], skip_e;
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();
        int nxt_pos = *upper_bound(all(skip_e), lets['e'][taken]);
        //cout << "pos = " << pos << " taken = " << taken << " nxt_taken = " << nxt_taken << " nxt_pos = " << nxt_pos << endl;
        ans = (pos - lets['e'][taken]) + dp(nxt_pos, nxt_taken);
    }

    rep(i, 'a', 'k') {
        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));
    }

    //cout << "pos = " << pos << " taken = " << taken << " ans = " << ans << endl;
    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);
        if (str[i] != 'e') skip_e.pb(i);
    }
    cnt = sz(lets['e']);

    cout << dp(0, 0) + cnt << endl;
    return 0;
}

Compilation message

vim.cpp: In function 'int main()':
vim.cpp:70:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   70 |         lets[str[i]].pb(i);
      |                    ^

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 98096 KB Output is correct
2 Correct 46 ms 98144 KB Output is correct
3 Correct 42 ms 98192 KB Output is correct
4 Correct 48 ms 98096 KB Output is correct
5 Correct 47 ms 98164 KB Output is correct
6 Correct 55 ms 98192 KB Output is correct
7 Correct 50 ms 98124 KB Output is correct
8 Correct 37 ms 98096 KB Output is correct
9 Correct 37 ms 98116 KB Output is correct
10 Correct 38 ms 98124 KB Output is correct
11 Correct 38 ms 98180 KB Output is correct
12 Correct 36 ms 98144 KB Output is correct
13 Correct 48 ms 98212 KB Output is correct
14 Correct 44 ms 98188 KB Output is correct
15 Correct 42 ms 98192 KB Output is correct
16 Correct 44 ms 98124 KB Output is correct
17 Correct 46 ms 98192 KB Output is correct
18 Correct 43 ms 98204 KB Output is correct
19 Correct 43 ms 98184 KB Output is correct
20 Correct 43 ms 98080 KB Output is correct
21 Correct 46 ms 98084 KB Output is correct
22 Correct 54 ms 98100 KB Output is correct
23 Correct 46 ms 98204 KB Output is correct
24 Correct 45 ms 98168 KB Output is correct
25 Correct 46 ms 98168 KB Output is correct
26 Correct 46 ms 98124 KB Output is correct
27 Correct 52 ms 98108 KB Output is correct
28 Correct 47 ms 98244 KB Output is correct
29 Correct 51 ms 98160 KB Output is correct
30 Correct 45 ms 98116 KB Output is correct
31 Correct 49 ms 98140 KB Output is correct
32 Correct 47 ms 98168 KB Output is correct
33 Correct 47 ms 98112 KB Output is correct
34 Correct 50 ms 98252 KB Output is correct
35 Correct 51 ms 98192 KB Output is correct
36 Correct 49 ms 98116 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 739 ms 98416 KB Output is correct
2 Correct 1592 ms 98336 KB Output is correct
3 Correct 322 ms 98244 KB Output is correct
4 Correct 732 ms 98344 KB Output is correct
5 Correct 1580 ms 98376 KB Output is correct
6 Correct 1164 ms 98376 KB Output is correct
7 Correct 984 ms 98244 KB Output is correct
8 Correct 945 ms 98284 KB Output is correct
9 Correct 1673 ms 98368 KB Output is correct
10 Correct 1491 ms 98408 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 119 ms 200388 KB Execution killed with signal 11
2 Runtime error 151 ms 200520 KB Execution killed with signal 11
3 Runtime error 123 ms 200640 KB Execution killed with signal 11
4 Runtime error 121 ms 200764 KB Execution killed with signal 11
5 Runtime error 116 ms 200512 KB Execution killed with signal 11
6 Runtime error 119 ms 200256 KB Execution killed with signal 11
7 Runtime error 117 ms 200356 KB Execution killed with signal 11
8 Runtime error 118 ms 200256 KB Execution killed with signal 11
9 Runtime error 119 ms 200224 KB Execution killed with signal 11
10 Runtime error 120 ms 200152 KB Execution killed with signal 11
11 Runtime error 116 ms 200680 KB Execution killed with signal 11
12 Runtime error 113 ms 200512 KB Execution killed with signal 11
13 Runtime error 124 ms 200912 KB Execution killed with signal 11
14 Runtime error 115 ms 200688 KB Execution killed with signal 11
15 Runtime error 121 ms 200380 KB Execution killed with signal 11
16 Runtime error 126 ms 200640 KB Execution killed with signal 11
17 Runtime error 119 ms 200340 KB Execution killed with signal 11
18 Runtime error 117 ms 200584 KB Execution killed with signal 11
19 Runtime error 126 ms 200504 KB Execution killed with signal 11
20 Runtime error 119 ms 200268 KB Execution killed with signal 11