Submission #895873

#	Time	Username	Problem	Language	Result	Execution time	Memory
895873		noompty	Vim (BOI13_vim)	C++17	69.50 / 100	26 ms	75972 KiB

vim

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
 
int n, sz, cnt, f[80005][15], g[80005][15][15], key[80005];
char s[80005];
 
int main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
    for (int i = 1, tmp = 0; i <= n; i++) {
        char c; cin >> c;
        if (c == 'e') {
            tmp = ++cnt;
        } else {
            key[++sz] = tmp;
            s[sz] = c - 'a';
            tmp = 0;
        }
    }
 
    memset(f, 0x3f, sizeof f);
    memset(g, 0x3f, sizeof g);
 
    f[0][s[1]] = 0;
    for (int i = 1; i <= sz; i++) {
        for (int j = 0; j < 10; j++) {
            if (j != s[i]) {
                if (!key[i]) {
                    f[i][j] = f[i - 1][j];
                }
                f[i][j] = min(f[i][j], g[i - 1][s[i]][j]);
            }
            f[i][j] = min(f[i][j], min(f[i - 1][s[i]], g[i - 1][s[i]][s[i]]) + 2);
            for (int k = 0; k < 10; k++) {
                if (j != s[i] && k != s[i]) {
                    g[i][j][k] = g[i - 1][j][k] + 1;
                }
                if (j != s[i]) {
                    g[i][j][k] = min(g[i][j][k], min(f[i - 1][j], g[i - 1][j][s[i]]) + 3);                    
                }
                if (k != s[i]) {
                    g[i][j][k] = min(g[i][j][k], g[i - 1][s[i]][k] + 3);
                }
                g[i][j][k] = min(g[i][j][k], min(f[i - 1][s[i]], g[i - 1][s[i]][s[i]]) + 5);
            }
        }
    }
 
    cout << f[sz][9] + (2 * cnt) - 2 << "\n";
 
}

Compilation message (stderr)

vim.cpp: In function 'int main()':
vim.cpp:30:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   30 |     f[0][s[1]] = 0;
      |          ~~~^
vim.cpp:37:52: warning: array subscript has type 'char' [-Wchar-subscripts]
   37 |                 f[i][j] = min(f[i][j], g[i - 1][s[i]][j]);
      |                                                 ~~~^
vim.cpp:39:52: warning: array subscript has type 'char' [-Wchar-subscripts]
   39 |             f[i][j] = min(f[i][j], min(f[i - 1][s[i]], g[i - 1][s[i]][s[i]]) + 2);
      |                                                 ~~~^
vim.cpp:39:68: warning: array subscript has type 'char' [-Wchar-subscripts]
   39 |             f[i][j] = min(f[i][j], min(f[i - 1][s[i]], g[i - 1][s[i]][s[i]]) + 2);
      |                                                                 ~~~^
vim.cpp:39:74: warning: array subscript has type 'char' [-Wchar-subscripts]
   39 |             f[i][j] = min(f[i][j], min(f[i - 1][s[i]], g[i - 1][s[i]][s[i]]) + 2);
      |                                                                       ~~~^
vim.cpp:45:82: warning: array subscript has type 'char' [-Wchar-subscripts]
   45 |                     g[i][j][k] = min(g[i][j][k], min(f[i - 1][j], g[i - 1][j][s[i]]) + 3);
      |                                                                               ~~~^
vim.cpp:48:62: warning: array subscript has type 'char' [-Wchar-subscripts]
   48 |                     g[i][j][k] = min(g[i][j][k], g[i - 1][s[i]][k] + 3);
      |                                                           ~~~^
vim.cpp:50:62: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |                 g[i][j][k] = min(g[i][j][k], min(f[i - 1][s[i]], g[i - 1][s[i]][s[i]]) + 5);
      |                                                           ~~~^
vim.cpp:50:78: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |                 g[i][j][k] = min(g[i][j][k], min(f[i - 1][s[i]], g[i - 1][s[i]][s[i]]) + 5);
      |                                                                           ~~~^
vim.cpp:50:84: warning: array subscript has type 'char' [-Wchar-subscripts]
   50 |                 g[i][j][k] = min(g[i][j][k], min(f[i - 1][s[i]], g[i - 1][s[i]][s[i]]) + 5);
      |                                                                                 ~~~^

• Subtask 1: 37.5 / 50
• Subtask 2: 8 / 10
• Subtask 3: 24 / 40