Submission #393287

#	Time	Username	Problem	Language	Result	Execution time	Memory
393287		JimmyZJX	Mountains (IOI17_mountains)	C++14	0 / 100	9 ms	15980 KiB

mountains

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <numeric>

using namespace std;

typedef long long LL;
typedef vector<int> Vi;
typedef vector<LL> VL;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;

#define forR(i, n) for (int i = 0; i < (n); i++)

template <typename T>
vector<size_t> sort_indexes(vector<T> v) {
	vector<size_t> idx(v.size());
	iota(idx.begin(), idx.end(), 0);

	stable_sort(idx.begin(), idx.end(),
		[&v](size_t i1, size_t i2) {return v[i1] < v[i2]; });

	return idx;
}

int see[2003][2003];
bool used[2003];

struct Frac { // a / b
	int a, b;
};

bool ge(Frac x, Frac y) {
	return (LL)x.a * y.b >= (LL)y.a * x.b;
}

int maximum_deevs(Vi y) {
	int n = y.size();
	memset(see, 0, sizeof(see));
	memset(used, 0, sizeof(used));

	Vi cnt(n);

	forR(i, n) {
		Frac view{ INT_MIN, 1 };
		for (int j = i - 1; j >= 0; j--) {
			Frac vj{ y[j] - y[i], i - j };
			if (ge(vj, view)) {
				view = vj;
				see[i][j] = 1;
				cnt[i]++;
			}
		}
		view = { INT_MIN, 1 };
		for (int j = i + 1; j < n; j++) {
			Frac vj{ y[j] - y[i], j - i };
			if (ge(vj, view)) {
				view = vj;
				see[i][j] = 1;
				cnt[i]++;
			}
		}
	}

	int ans = 0;

	auto idx = sort_indexes(cnt);
	for (int i : idx) {
		if (!used[i]) {
			ans++;
			used[i] = true;
			forR(j, n) {
				if (see[i][j]) {
					used[j] = true;
				}
			}
		}
	}

	return ans;
}


#ifdef TEST_LOCAL
int main() {
	auto r = maximum_deevs(Vi{ 0,1,1000000,1500001,1499997,1499992,1499986,1499979,1499971,1499962,1499952,1499941,1499929,1499916,1499902,1499887,1499871,1499854,1000000000 });

	return 0;
}
#endif

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30