oj.uz

답안 #491815

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
491815 2021-12-04T14:50:58 Z Victor Vim (BOI13_vim) C++17
13.8889 / 100
 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);
      |                             ^

Subtask #1
13.8888888889 / 50.0

# 결과 실행 시간 메모리 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

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 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

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 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