답안 #601329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
601329	2022-07-21T17:45:14 Z	GusterGoose27	Vim (BOI13_vim)	C++11	12.5 / 100	400 ms	150604 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];

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][mask|(1 << elems[i])];
		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;
	for (int i = n-1; i >= 0; i--) {
		for (int j = 0; j < 10; j++) nextocc[i][j] = seen[j];
		seen[elems[i]] = i;
	}
	stree *tree = new stree(0, n-1);
	for (int i = n-1; i >= 0; i--) {
		if (nextocc[i][9] == n) {
			for (int mask = 0; mask < (1<<9); mask++) {
				dp[i][mask] = 0;
			}
			dq[i] = 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], 2+dq[nextpos]+nextpos-i);
			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(le, nextpos));
			nextdp[j] += min(dq[nextpos], dp[nextpos][allow]);
		}
		make_dp(i);
	}
	cout << (nume+dp[0][(1 << 9)-1]) << "\n";
}

Subtask #1
12.5 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1364 KB	Output is correct
2	Incorrect	3 ms	1236 KB	Output isn't correct
3	Incorrect	2 ms	1108 KB	Output isn't correct
4	Incorrect	2 ms	1224 KB	Output isn't correct
5	Correct	2 ms	1236 KB	Output is correct
6	Incorrect	3 ms	1352 KB	Output isn't correct
7	Incorrect	3 ms	1356 KB	Output isn't correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	328 KB	Output is correct
10	Incorrect	1 ms	340 KB	Output isn't correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	3 ms	1360 KB	Output is correct
14	Incorrect	3 ms	1236 KB	Output isn't correct
15	Incorrect	2 ms	1096 KB	Output isn't correct
16	Incorrect	2 ms	1236 KB	Output isn't correct
17	Incorrect	3 ms	1364 KB	Output isn't correct
18	Incorrect	2 ms	1108 KB	Output isn't correct
19	Correct	3 ms	1108 KB	Output is correct
20	Incorrect	3 ms	1108 KB	Output isn't correct
21	Incorrect	3 ms	1236 KB	Output isn't correct
22	Correct	3 ms	1228 KB	Output is correct
23	Incorrect	3 ms	1364 KB	Output isn't correct
24	Incorrect	3 ms	1236 KB	Output isn't correct
25	Incorrect	3 ms	1236 KB	Output isn't correct
26	Incorrect	4 ms	1236 KB	Output isn't correct
27	Incorrect	4 ms	1364 KB	Output isn't correct
28	Incorrect	3 ms	1364 KB	Output isn't correct
29	Incorrect	3 ms	1364 KB	Output isn't correct
30	Incorrect	3 ms	1352 KB	Output isn't correct
31	Incorrect	3 ms	1236 KB	Output isn't correct
32	Incorrect	3 ms	1364 KB	Output isn't correct
33	Incorrect	3 ms	1364 KB	Output isn't correct
34	Incorrect	3 ms	1224 KB	Output isn't correct
35	Incorrect	2 ms	1236 KB	Output isn't correct
36	Incorrect	3 ms	1364 KB	Output isn't correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	27 ms	11044 KB	Output isn't correct
2	Incorrect	27 ms	10968 KB	Output isn't correct
3	Incorrect	15 ms	6376 KB	Output isn't correct
4	Incorrect	35 ms	10828 KB	Output isn't correct
5	Incorrect	29 ms	10832 KB	Output isn't correct
6	Incorrect	28 ms	11020 KB	Output isn't correct
7	Incorrect	26 ms	10888 KB	Output isn't correct
8	Incorrect	26 ms	10840 KB	Output isn't correct
9	Incorrect	30 ms	11084 KB	Output isn't correct
10	Incorrect	32 ms	10956 KB	Output isn't correct

Subtask #3
0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	349 ms	129960 KB	Output isn't correct
2	Incorrect	287 ms	127280 KB	Output isn't correct
3	Incorrect	305 ms	130576 KB	Output isn't correct
4	Incorrect	359 ms	150604 KB	Output isn't correct
5	Incorrect	380 ms	149952 KB	Output isn't correct
6	Incorrect	353 ms	132272 KB	Output isn't correct
7	Incorrect	373 ms	137448 KB	Output isn't correct
8	Incorrect	371 ms	140096 KB	Output isn't correct
9	Incorrect	386 ms	138972 KB	Output isn't correct
10	Incorrect	359 ms	140648 KB	Output isn't correct
11	Incorrect	349 ms	150564 KB	Output isn't correct
12	Incorrect	400 ms	149968 KB	Output isn't correct
13	Incorrect	356 ms	145660 KB	Output isn't correct
14	Incorrect	336 ms	147200 KB	Output isn't correct
15	Incorrect	385 ms	148920 KB	Output isn't correct
16	Incorrect	347 ms	128316 KB	Output isn't correct
17	Incorrect	333 ms	129868 KB	Output isn't correct
18	Incorrect	320 ms	130540 KB	Output isn't correct
19	Incorrect	293 ms	127152 KB	Output isn't correct
20	Incorrect	329 ms	128884 KB	Output isn't correct

답안 #601329

Compilation message

Subtask #1 12.5 / 50.0

Subtask #2 0 / 10.0

Subtask #3 0 / 40.0

Subtask #1
12.5 / 50.0

Subtask #2
0 / 10.0

Subtask #3
0 / 40.0