답안 #206679

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
206679	2020-03-04T12:41:45 Z	opukittpceno_hhr	Rope (JOI17_rope)	C++17	15 / 100	1569 ms	508 KB

rope

#ifndef LOCAL
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#endif

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <random>
#include <functional>

using namespace std;

const int N = 15;

int dp[N][N + 1];
int sdp[N + 1];
int pdp[N + 1];

int ts[N];
int s[N + 1];

int can(int i, int len) {
	if (len % 2 == 1) {
		return 0;
	}
	if (len == 0) {
		return 1;
	}
	if (dp[i][len] == -1) {
		dp[i][len] = can(i + 1, len - 2) & ((ts[i] == ts[i + len - 1]));
	}
	return dp[i][len];
}

void ref() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= N; j++) {
			dp[i][j] = -1;
		}
	}
}

int cans(int n) {
	ref();
	fill(pdp, pdp + N + 1, 0);
	fill(sdp, sdp + N + 1, 0);
	pdp[0] = 1;
	sdp[0] = 1;
	for (int i = 0; i < n; i++) {
		for (int len = 2; i + len <= n; len++) {
			pdp[i + len / 2] |= (pdp[i] & can(i, len));
		}
	}
	reverse(ts, ts + n);
	ref();
	for (int i = 0; i < n; i++) {
		for (int len = 2; i + len <= n; len++) {
			sdp[i + len / 2] |= (sdp[i] & can(i, len));
		}
	}
	for (int i = 0; i <= n; i++) {
		if (n - 2 - i >= 0) {
			if (pdp[i] & sdp[n - 2 - i]) return 1;
		}
	}
	return 0;
}


int solve(int n, int a, int b) {
	int ans = n;
	for (int i = 0; i < (1 << n); i++) {
		for (int j = 0; j < n; j++) {
			if ((i >> j) & 1) {
				ts[j] = a;
			} else {
				ts[j] = b;
			}
		}
		if (cans(n)) {
			int c = 0;
			for (int j = 0; j < n; j++) {
				c += (s[j] != ts[j]);
			}
			ans = min(ans, c);
		}
	}
	return ans;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		s[i]--;
	}
	vector<int> ans(m, n);
	for (int i = 0; i < m; i++) {
		for (int j = i; j < m; j++) {
			int v = solve(n, i, j);
			ans[i] = min(ans[i], v);
			ans[j] = min(ans[j], v);
		}
	}
	for (auto t : ans) {
		cout << t << '\n';
	}
}

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1569 ms	376 KB	Output is correct
2	Correct	132 ms	376 KB	Output is correct
3	Correct	317 ms	376 KB	Output is correct
4	Correct	304 ms	504 KB	Output is correct
5	Correct	81 ms	376 KB	Output is correct
6	Correct	315 ms	388 KB	Output is correct
7	Correct	570 ms	384 KB	Output is correct
8	Correct	798 ms	508 KB	Output is correct
9	Correct	615 ms	384 KB	Output is correct
10	Correct	441 ms	376 KB	Output is correct
11	Correct	28 ms	376 KB	Output is correct
12	Correct	30 ms	504 KB	Output is correct
13	Correct	21 ms	376 KB	Output is correct
14	Correct	6 ms	376 KB	Output is correct
15	Correct	6 ms	376 KB	Output is correct
16	Correct	7 ms	376 KB	Output is correct
17	Correct	24 ms	376 KB	Output is correct
18	Correct	17 ms	376 KB	Output is correct
19	Correct	16 ms	504 KB	Output is correct
20	Correct	11 ms	376 KB	Output is correct
21	Correct	5 ms	376 KB	Output is correct
22	Correct	5 ms	376 KB	Output is correct
23	Correct	5 ms	376 KB	Output is correct
24	Correct	4 ms	376 KB	Output is correct
25	Correct	5 ms	376 KB	Output is correct
26	Correct	5 ms	376 KB	Output is correct

Subtask #2
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1569 ms	376 KB	Output is correct
2	Correct	132 ms	376 KB	Output is correct
3	Correct	317 ms	376 KB	Output is correct
4	Correct	304 ms	504 KB	Output is correct
5	Correct	81 ms	376 KB	Output is correct
6	Correct	315 ms	388 KB	Output is correct
7	Correct	570 ms	384 KB	Output is correct
8	Correct	798 ms	508 KB	Output is correct
9	Correct	615 ms	384 KB	Output is correct
10	Correct	441 ms	376 KB	Output is correct
11	Correct	28 ms	376 KB	Output is correct
12	Correct	30 ms	504 KB	Output is correct
13	Correct	21 ms	376 KB	Output is correct
14	Correct	6 ms	376 KB	Output is correct
15	Correct	6 ms	376 KB	Output is correct
16	Correct	7 ms	376 KB	Output is correct
17	Correct	24 ms	376 KB	Output is correct
18	Correct	17 ms	376 KB	Output is correct
19	Correct	16 ms	504 KB	Output is correct
20	Correct	11 ms	376 KB	Output is correct
21	Correct	5 ms	376 KB	Output is correct
22	Correct	5 ms	376 KB	Output is correct
23	Correct	5 ms	376 KB	Output is correct
24	Correct	4 ms	376 KB	Output is correct
25	Correct	5 ms	376 KB	Output is correct
26	Correct	5 ms	376 KB	Output is correct
27	Runtime error	5 ms	480 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Halted	0 ms	0 KB	-

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1569 ms	376 KB	Output is correct
2	Correct	132 ms	376 KB	Output is correct
3	Correct	317 ms	376 KB	Output is correct
4	Correct	304 ms	504 KB	Output is correct
5	Correct	81 ms	376 KB	Output is correct
6	Correct	315 ms	388 KB	Output is correct
7	Correct	570 ms	384 KB	Output is correct
8	Correct	798 ms	508 KB	Output is correct
9	Correct	615 ms	384 KB	Output is correct
10	Correct	441 ms	376 KB	Output is correct
11	Correct	28 ms	376 KB	Output is correct
12	Correct	30 ms	504 KB	Output is correct
13	Correct	21 ms	376 KB	Output is correct
14	Correct	6 ms	376 KB	Output is correct
15	Correct	6 ms	376 KB	Output is correct
16	Correct	7 ms	376 KB	Output is correct
17	Correct	24 ms	376 KB	Output is correct
18	Correct	17 ms	376 KB	Output is correct
19	Correct	16 ms	504 KB	Output is correct
20	Correct	11 ms	376 KB	Output is correct
21	Correct	5 ms	376 KB	Output is correct
22	Correct	5 ms	376 KB	Output is correct
23	Correct	5 ms	376 KB	Output is correct
24	Correct	4 ms	376 KB	Output is correct
25	Correct	5 ms	376 KB	Output is correct
26	Correct	5 ms	376 KB	Output is correct
27	Runtime error	5 ms	480 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Halted	0 ms	0 KB	-

Subtask #4
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1569 ms	376 KB	Output is correct
2	Correct	132 ms	376 KB	Output is correct
3	Correct	317 ms	376 KB	Output is correct
4	Correct	304 ms	504 KB	Output is correct
5	Correct	81 ms	376 KB	Output is correct
6	Correct	315 ms	388 KB	Output is correct
7	Correct	570 ms	384 KB	Output is correct
8	Correct	798 ms	508 KB	Output is correct
9	Correct	615 ms	384 KB	Output is correct
10	Correct	441 ms	376 KB	Output is correct
11	Correct	28 ms	376 KB	Output is correct
12	Correct	30 ms	504 KB	Output is correct
13	Correct	21 ms	376 KB	Output is correct
14	Correct	6 ms	376 KB	Output is correct
15	Correct	6 ms	376 KB	Output is correct
16	Correct	7 ms	376 KB	Output is correct
17	Correct	24 ms	376 KB	Output is correct
18	Correct	17 ms	376 KB	Output is correct
19	Correct	16 ms	504 KB	Output is correct
20	Correct	11 ms	376 KB	Output is correct
21	Correct	5 ms	376 KB	Output is correct
22	Correct	5 ms	376 KB	Output is correct
23	Correct	5 ms	376 KB	Output is correct
24	Correct	4 ms	376 KB	Output is correct
25	Correct	5 ms	376 KB	Output is correct
26	Correct	5 ms	376 KB	Output is correct
27	Runtime error	5 ms	480 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1569 ms	376 KB	Output is correct
2	Correct	132 ms	376 KB	Output is correct
3	Correct	317 ms	376 KB	Output is correct
4	Correct	304 ms	504 KB	Output is correct
5	Correct	81 ms	376 KB	Output is correct
6	Correct	315 ms	388 KB	Output is correct
7	Correct	570 ms	384 KB	Output is correct
8	Correct	798 ms	508 KB	Output is correct
9	Correct	615 ms	384 KB	Output is correct
10	Correct	441 ms	376 KB	Output is correct
11	Correct	28 ms	376 KB	Output is correct
12	Correct	30 ms	504 KB	Output is correct
13	Correct	21 ms	376 KB	Output is correct
14	Correct	6 ms	376 KB	Output is correct
15	Correct	6 ms	376 KB	Output is correct
16	Correct	7 ms	376 KB	Output is correct
17	Correct	24 ms	376 KB	Output is correct
18	Correct	17 ms	376 KB	Output is correct
19	Correct	16 ms	504 KB	Output is correct
20	Correct	11 ms	376 KB	Output is correct
21	Correct	5 ms	376 KB	Output is correct
22	Correct	5 ms	376 KB	Output is correct
23	Correct	5 ms	376 KB	Output is correct
24	Correct	4 ms	376 KB	Output is correct
25	Correct	5 ms	376 KB	Output is correct
26	Correct	5 ms	376 KB	Output is correct
27	Runtime error	5 ms	480 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Halted	0 ms	0 KB	-

답안 #206679

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 0 / 30.0

Subtask #3 0 / 10.0

Subtask #4 0 / 25.0

Subtask #5 0 / 20.0

Subtask #1
15.0 / 15.0

Subtask #2
0 / 30.0

Subtask #3
0 / 10.0

Subtask #4
0 / 25.0

Subtask #5
0 / 20.0