Submission #310000

#	Time	Username	Problem	Language	Result	Execution time	Memory
310000		ttnhuy313	Mountains (IOI17_mountains)	C++14	20 / 100	353 ms	504 KiB

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 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30