oj.uz

답안 #491811

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

Subtask #1
13.8888888889 / 50.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 40.0

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