답안 #601375

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
601375 2022-07-21T19:18:48 Z GusterGoose27 Vim (BOI13_vim) C++11
26.3889 / 100
276 ms 150816 KB
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 70000;
const int inf = 1e9;
int n;
int dp[MAXN][1 << 9]; // dont return to i
int dq[MAXN]; // return to i
int elems[MAXN];
int nextocc[MAXN][10];
bool ise[MAXN];
int nextdp[9];
int avail[MAXN+1];

class stree {
public:
	stree *l = nullptr;
	stree *r = nullptr;
	int lp, rp;
	int mne;
	int cont_mask = 0;
	stree(int lv, int rv) {
		lp = lv;
		rp = rv;
		if (lp == rp) {
			if (ise[lp]) mne = lp;
			else mne = n;
			if (elems[lp] < 9) cont_mask = (1 << elems[lp]);
		}
		else {
			int m = (lp+rp)/2;
			l = new stree(lp, m);
			r = new stree(m+1, rp);
			mne = min(l->mne, r->mne);
			cont_mask = l->cont_mask | r->cont_mask;
		}
	}
	int query(int lv, int rv) {
		if (lp > rv || rp < lv) return n;
		if (lp >= lv && rp <= rv) return mne;
		return min(l->query(lv, rv), r->query(lv, rv));
	}
	int get_cont(int lv, int rv) {
		if (lp > rv || rp < lv) return 0;
		if (lp >= lv && rp <= rv) return cont_mask;
		return l->get_cont(lv, rv) | r->get_cont(lv, rv);
	}
};

void make_dp(int i, int pos = 0, int mask = 0, int best = inf) {
	if (pos == 9) {
		int other = inf;
		if (mask & (1 << elems[i]) == 0) other = 2+dp[i][(1<<9)-1];
		dp[i][mask] = min(other, best);
		return;
	}
	make_dp(i, pos+1, mask+(1<<pos), min(best, nextdp[pos]));
	make_dp(i, pos+1, mask, best);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	string s; cin >> s;
	int nume = 0;
	for (int i = 0; i < n; i++) {
		int v = s[i]-'a';
		if (v == 4) {
			ise[i] = 1;
			v = 10;
		}
		if (v > 4) v--;
		elems[i] = v;
		nume += ise[i];
	}
	int seen[10];
	for (int i = 0; i < 10; i++) seen[i] = n;
	avail[n] = n;
	for (int i = n-1; i >= 0; i--) {
		for (int j = 0; j < 10; j++) nextocc[i][j] = seen[j];
		seen[elems[i]] = i;
		avail[i] = avail[i+1];
		if (elems[i] < 9) avail[i] = i;
	}
	stree *tree = new stree(0, n-1);
	for (int i = n-1; i >= 0; i--) {
		if (elems[i] == 9) continue;
		if (nextocc[i][9] == n) {
			for (int mask = 0; mask < (1<<9); mask++) {
				dp[i][mask] = 0;
			}
			dq[i] = 0;
			continue;
		}
		dq[i] = inf;
		for (int j = 0; j < 9; j++) {
			int nextpos = nextocc[i][j];
			if (nextpos == n) {
				nextdp[j] = inf;
				continue;
			}
			dq[i] = min(dq[i], dq[nextpos]+nextpos-i+2);
			int le = tree->query(i, nextpos);
			if (le == n) {
				nextdp[j] = 2+dp[nextpos][(1 << 9)-1];
				continue;
			}
			nextdp[j] = 2+nextpos-le;
			if (nextocc[nextpos][9] == n) continue;
			int allow = ((1 << 9)-1)^(tree->get_cont(avail[le]+1, nextpos));
			nextdp[j] += min(dq[nextpos], dp[nextpos][allow]);
		}
		make_dp(i);
	}
	cout << (nume+dp[0][(1 << 9)-1]) << "\n";
}

Compilation message

vim.cpp: In function 'void make_dp(int, int, int, int)':
vim.cpp:54:30: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   54 |   if (mask & (1 << elems[i]) == 0) other = 2+dp[i][(1<<9)-1];
      |              ~~~~~~~~~~~~~~~~^~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1236 KB Output is correct
2 Incorrect 2 ms 1236 KB Output isn't correct
3 Incorrect 1 ms 1108 KB Output isn't correct
4 Incorrect 2 ms 1236 KB Output isn't correct
5 Correct 2 ms 1236 KB Output is correct
6 Incorrect 2 ms 1364 KB Output isn't correct
7 Incorrect 2 ms 1364 KB Output isn't correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 2 ms 1236 KB Output is correct
14 Incorrect 2 ms 1236 KB Output isn't correct
15 Incorrect 2 ms 1108 KB Output isn't correct
16 Incorrect 3 ms 1236 KB Output isn't correct
17 Correct 3 ms 1364 KB Output is correct
18 Incorrect 2 ms 1108 KB Output isn't correct
19 Correct 1 ms 1108 KB Output is correct
20 Correct 2 ms 1108 KB Output is correct
21 Incorrect 2 ms 1236 KB Output isn't correct
22 Correct 2 ms 1236 KB Output is correct
23 Incorrect 2 ms 1364 KB Output isn't correct
24 Incorrect 2 ms 1236 KB Output isn't correct
25 Correct 2 ms 1236 KB Output is correct
26 Correct 2 ms 1236 KB Output is correct
27 Correct 2 ms 1364 KB Output is correct
28 Incorrect 2 ms 1364 KB Output isn't correct
29 Correct 2 ms 1364 KB Output is correct
30 Incorrect 2 ms 1364 KB Output isn't correct
31 Correct 2 ms 1236 KB Output is correct
32 Incorrect 3 ms 1364 KB Output isn't correct
33 Correct 2 ms 1364 KB Output is correct
34 Correct 3 ms 1236 KB Output is correct
35 Incorrect 2 ms 1236 KB Output isn't correct
36 Incorrect 2 ms 1364 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 9664 KB Output isn't correct
2 Incorrect 16 ms 11068 KB Output isn't correct
3 Incorrect 8 ms 5940 KB Output isn't correct
4 Incorrect 12 ms 9684 KB Output isn't correct
5 Incorrect 17 ms 10904 KB Output isn't correct
6 Incorrect 20 ms 10964 KB Output isn't correct
7 Incorrect 15 ms 10316 KB Output isn't correct
8 Incorrect 15 ms 10196 KB Output isn't correct
9 Incorrect 17 ms 11060 KB Output isn't correct
10 Incorrect 21 ms 11100 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 263 ms 130044 KB Output isn't correct
2 Incorrect 215 ms 127416 KB Output isn't correct
3 Incorrect 248 ms 130676 KB Output isn't correct
4 Incorrect 243 ms 150764 KB Output isn't correct
5 Incorrect 276 ms 150160 KB Output isn't correct
6 Incorrect 153 ms 115916 KB Output isn't correct
7 Incorrect 223 ms 137536 KB Output isn't correct
8 Incorrect 258 ms 140212 KB Output isn't correct
9 Incorrect 204 ms 133396 KB Output isn't correct
10 Incorrect 196 ms 132760 KB Output isn't correct
11 Incorrect 247 ms 150816 KB Output isn't correct
12 Incorrect 272 ms 150136 KB Output isn't correct
13 Incorrect 266 ms 145792 KB Output isn't correct
14 Incorrect 258 ms 147520 KB Output isn't correct
15 Incorrect 237 ms 149152 KB Output isn't correct
16 Incorrect 232 ms 128668 KB Output isn't correct
17 Incorrect 238 ms 130068 KB Output isn't correct
18 Incorrect 234 ms 130636 KB Output isn't correct
19 Incorrect 213 ms 127332 KB Output isn't correct
20 Incorrect 221 ms 129008 KB Output isn't correct