Submission #310000

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
310000	2020-10-05T09:32:00 Z	ttnhuy313	Mountains (IOI17_mountains)	C++14	20 / 100	353 ms	504 KB

mountains

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define sqr(a) (a * a)
typedef pair <int, int> ii;

const int N = 2005;
int dp[N][N];

int cross(ii a, ii b) {
	return a.first * b.second - a.second * b.first;
}

bool ccw(ii a, ii b, ii c) {
	return cross(ii(b.first - a.first, b.second - a.second), ii(c.first - a.first, c.second - a.second)) > 0;
}

int maximum_deevs(vector <int32_t> y) {
	int n = y.size(), ret = 0;
	for (int mask = 0; mask < (1 << n); ++mask) {
		int t = __builtin_popcount(mask);
		for (int i = 0; i < n; ++i) if (mask & (1 << i)) {
			for (int j = i + 1; j < n; ++j) if (mask & (1 << j)) {
				bool ok = false;
				for (int k = i + 1; k < j; ++k) if (ccw(ii(j, y[j]), ii(k, y[k]), ii(i, y[i]))) {
					ok = true;
				}
				if (!ok) t = -1;
			}
		}
		ret = max(ret, t);
	}

	return ret;
}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	342 ms	376 KB	Output is correct
7	Correct	348 ms	256 KB	Output is correct
8	Correct	342 ms	364 KB	Output is correct
9	Correct	344 ms	376 KB	Output is correct
10	Correct	152 ms	256 KB	Output is correct
11	Correct	348 ms	376 KB	Output is correct
12	Correct	353 ms	376 KB	Output is correct
13	Correct	345 ms	496 KB	Output is correct
14	Correct	347 ms	504 KB	Output is correct
15	Correct	345 ms	380 KB	Output is correct
16	Correct	353 ms	376 KB	Output is correct

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	342 ms	376 KB	Output is correct
7	Correct	348 ms	256 KB	Output is correct
8	Correct	342 ms	364 KB	Output is correct
9	Correct	344 ms	376 KB	Output is correct
10	Correct	152 ms	256 KB	Output is correct
11	Correct	348 ms	376 KB	Output is correct
12	Correct	353 ms	376 KB	Output is correct
13	Correct	345 ms	496 KB	Output is correct
14	Correct	347 ms	504 KB	Output is correct
15	Correct	345 ms	380 KB	Output is correct
16	Correct	353 ms	376 KB	Output is correct
17	Incorrect	1 ms	256 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Subtask #3

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	342 ms	376 KB	Output is correct
7	Correct	348 ms	256 KB	Output is correct
8	Correct	342 ms	364 KB	Output is correct
9	Correct	344 ms	376 KB	Output is correct
10	Correct	152 ms	256 KB	Output is correct
11	Correct	348 ms	376 KB	Output is correct
12	Correct	353 ms	376 KB	Output is correct
13	Correct	345 ms	496 KB	Output is correct
14	Correct	347 ms	504 KB	Output is correct
15	Correct	345 ms	380 KB	Output is correct
16	Correct	353 ms	376 KB	Output is correct
17	Incorrect	1 ms	256 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Subtask #4

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	1 ms	256 KB	Output is correct
6	Correct	342 ms	376 KB	Output is correct
7	Correct	348 ms	256 KB	Output is correct
8	Correct	342 ms	364 KB	Output is correct
9	Correct	344 ms	376 KB	Output is correct
10	Correct	152 ms	256 KB	Output is correct
11	Correct	348 ms	376 KB	Output is correct
12	Correct	353 ms	376 KB	Output is correct
13	Correct	345 ms	496 KB	Output is correct
14	Correct	347 ms	504 KB	Output is correct
15	Correct	345 ms	380 KB	Output is correct
16	Correct	353 ms	376 KB	Output is correct
17	Incorrect	1 ms	256 KB	Output isn't correct
18	Halted	0 ms	0 KB	-