oj.uz

Submission #63237

# Submission time Handle Problem Language Result Execution time Memory
63237 2018-08-01T06:46:17 Z 강태규(#1831) Vim (BOI13_vim) C++11
60 / 100
 794 ms 205916 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n;
char in[70001];
int str[70000];
int ch[70000];
int f[70000][9];
vector<int> cr[9];
vector<int> nd;
int pr[70000];
int dp[5000][5000];

int upbound(vector<int> &v, int x) {
    vector<int>::iterator it = upper_bound(v.begin(), v.end(), x);
    if (it != v.end()) return *it;
    return x;
}

vector<pii> dist[20000];

const int inf = 1e8;
int main() {
    scanf("%*d%s", in);
    nd.push_back(0);
    int er = 0;
    for (int i = 0, fs = 0; in[i]; ++i) {
        if (in[i] == 'e') {
            er += 2;
            fs = 1;
        }
        else {
            if (fs) ch[n] = 1, fs = 0, nd.push_back(n);
            str[n] = in[i] - 'a';
            if (in[i] > 'e') --str[n];
            cr[str[n]].push_back(n);
            ++n;
        }
    }
    nd.push_back(n);
    for (int i = 1; i < nd.size(); ++i) {
        for (int j = nd[i - 1]; j < nd[i]; ++j) {
            pr[j] = i - 1;
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 9; ++j) {
            f[i][j] = upbound(cr[j], i);
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            dp[i][j] = 4 * n;
        }
    }
    dist[dp[0][0] = 0].emplace_back(0, 0);
    for (int d = 0; d < 4 * n; ++d) {
        for (int _i = 0; _i < dist[d].size(); ++_i) {
            int x, y;
            tie(x, y) = dist[d][_i];
            if (dp[x][y] != d) continue;
            if (y == nd.size() - 2) continue;
            for (int i = 0; i < 9; ++i) {
                int nx = f[x][i];
                if (d + 2 < dp[nx][y]) {
                    dist[dp[nx][y] = d + 2].emplace_back(nx, y);
                }
            }
            int px = nd[y + 1];
            if (x < px) continue;
            int py = pr[x];
            if (d + x - px < dp[px][py]) {
                dist[dp[px][py] = d + x - px].emplace_back(px, py);
            }
        }
    }
    
    int ans = 4 * n;
    for (int i = 0; i < n; ++i) {
        ans = min(ans, dp[i][nd.size() - 2]);
    }
    printf("%d\n", ans + er);
	return 0;
}

Compilation message

vim.cpp: In function 'int main()':
vim.cpp:58:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 1; i < nd.size(); ++i) {
                     ~~^~~~~~~~~~~
vim.cpp:75:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int _i = 0; _i < dist[d].size(); ++_i) {
                          ~~~^~~~~~~~~~~~~~~~
vim.cpp:79:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (y == nd.size() - 2) continue;
                 ~~^~~~~~~~~~~~~~~~
vim.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%*d%s", in);
     ~~~~~^~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2424 KB Output is correct
2 Correct 7 ms 3084 KB Output is correct
3 Correct 7 ms 3084 KB Output is correct
4 Correct 7 ms 3084 KB Output is correct
5 Correct 8 ms 3084 KB Output is correct
6 Correct 7 ms 3320 KB Output is correct
7 Correct 10 ms 3452 KB Output is correct
8 Correct 5 ms 3452 KB Output is correct
9 Correct 3 ms 3452 KB Output is correct
10 Correct 5 ms 3452 KB Output is correct
11 Correct 3 ms 3452 KB Output is correct
12 Correct 3 ms 3452 KB Output is correct
13 Correct 6 ms 3452 KB Output is correct
14 Correct 9 ms 3452 KB Output is correct
15 Correct 6 ms 3452 KB Output is correct
16 Correct 7 ms 3452 KB Output is correct
17 Correct 8 ms 3680 KB Output is correct
18 Correct 8 ms 3680 KB Output is correct
19 Correct 6 ms 3680 KB Output is correct
20 Correct 5 ms 3680 KB Output is correct
21 Correct 8 ms 3680 KB Output is correct
22 Correct 6 ms 3680 KB Output is correct
23 Correct 8 ms 3832 KB Output is correct
24 Correct 7 ms 3832 KB Output is correct
25 Correct 10 ms 3832 KB Output is correct
26 Correct 10 ms 3832 KB Output is correct
27 Correct 9 ms 3832 KB Output is correct
28 Correct 9 ms 3832 KB Output is correct
29 Correct 9 ms 3832 KB Output is correct
30 Correct 8 ms 3832 KB Output is correct
31 Correct 6 ms 3832 KB Output is correct
32 Correct 9 ms 3832 KB Output is correct
33 Correct 8 ms 3832 KB Output is correct
34 Correct 6 ms 3832 KB Output is correct
35 Correct 8 ms 3832 KB Output is correct
36 Correct 9 ms 3832 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 56208 KB Output is correct
2 Correct 703 ms 118460 KB Output is correct
3 Correct 130 ms 118460 KB Output is correct
4 Correct 288 ms 118460 KB Output is correct
5 Correct 676 ms 118460 KB Output is correct
6 Correct 643 ms 121032 KB Output is correct
7 Correct 351 ms 121032 KB Output is correct
8 Correct 357 ms 121032 KB Output is correct
9 Correct 576 ms 121032 KB Output is correct
10 Correct 794 ms 121316 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 365 ms 205160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 455 ms 205504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 375 ms 205628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 377 ms 205868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 419 ms 205868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 312 ms 205868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 364 ms 205868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 464 ms 205868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 356 ms 205868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 333 ms 205868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 375 ms 205868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 366 ms 205868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 389 ms 205868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 385 ms 205868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 350 ms 205868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 404 ms 205868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 398 ms 205868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 366 ms 205868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 314 ms 205868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 342 ms 205916 KB Execution killed with signal 11 (could be triggered by violating memory limits)