oj.uz

Submission #601351

# Submission time Handle Problem Language Result Execution time Memory
601351 2022-07-21T18:08:44 Z GusterGoose27 Vim (BOI13_vim) C++11
13.8889 / 100
 394 ms 150612 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<<9)-1)) 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;
	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
13.8888888889 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1364 KB Output is correct
2 Incorrect 3 ms 1272 KB Output isn't correct
3 Incorrect 2 ms 1108 KB Output isn't correct
4 Incorrect 3 ms 1188 KB Output isn't correct
5 Correct 4 ms 1236 KB Output is correct
6 Incorrect 3 ms 1376 KB Output isn't correct
7 Incorrect 4 ms 1320 KB Output isn't correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Incorrect 0 ms 340 KB Output isn't correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 276 KB Output is correct
13 Correct 3 ms 1364 KB Output is correct
14 Incorrect 2 ms 1236 KB Output isn't correct
15 Incorrect 3 ms 1108 KB Output isn't correct
16 Incorrect 3 ms 1236 KB Output isn't correct
17 Incorrect 4 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 Correct 2 ms 1108 KB Output is correct
21 Incorrect 3 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 3 ms 1236 KB Output isn't correct
25 Incorrect 3 ms 1236 KB Output isn't correct
26 Incorrect 3 ms 1236 KB Output isn't correct
27 Incorrect 3 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 1364 KB Output isn't correct
31 Incorrect 3 ms 1276 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 1216 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

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 10896 KB Output isn't correct
2 Incorrect 28 ms 11016 KB Output isn't correct
3 Incorrect 16 ms 6280 KB Output isn't correct
4 Incorrect 29 ms 10896 KB Output isn't correct
5 Incorrect 28 ms 10876 KB Output isn't correct
6 Incorrect 33 ms 10928 KB Output isn't correct
7 Incorrect 29 ms 10876 KB Output isn't correct
8 Incorrect 35 ms 10788 KB Output isn't correct
9 Incorrect 35 ms 10968 KB Output isn't correct
10 Incorrect 31 ms 11052 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 340 ms 129876 KB Output isn't correct
2 Incorrect 305 ms 127180 KB Output isn't correct
3 Incorrect 314 ms 130548 KB Output isn't correct
4 Incorrect 361 ms 150552 KB Output isn't correct
5 Incorrect 366 ms 150084 KB Output isn't correct
6 Incorrect 344 ms 132196 KB Output isn't correct
7 Incorrect 338 ms 137300 KB Output isn't correct
8 Incorrect 394 ms 139912 KB Output isn't correct
9 Incorrect 368 ms 138752 KB Output isn't correct
10 Incorrect 351 ms 140604 KB Output isn't correct
11 Incorrect 359 ms 150612 KB Output isn't correct
12 Incorrect 372 ms 149912 KB Output isn't correct
13 Incorrect 339 ms 145532 KB Output isn't correct
14 Incorrect 350 ms 147260 KB Output isn't correct
15 Incorrect 381 ms 148784 KB Output isn't correct
16 Incorrect 357 ms 128188 KB Output isn't correct
17 Incorrect 392 ms 129920 KB Output isn't correct
18 Incorrect 309 ms 130548 KB Output isn't correct
19 Incorrect 337 ms 127200 KB Output isn't correct
20 Incorrect 326 ms 128880 KB Output isn't correct