oj.uz

Submission #393156

# Submission time Handle Problem Language Result Execution time Memory
393156 2021-04-22T20:30:37 Z JimmyZJX Mountains (IOI17_mountains) C++14
0 / 100
 10 ms 15952 KB 
#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 x.a * y.b >= y.a * x.b;
}

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

	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;
			}
		}
		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;
			}
		}
	}

	int ans = 0;

	auto idx = sort_indexes(y);
	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{ 6, 1, 5, 2, 3, 1 });

	return 0;
}
#endif

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15952 KB Output is correct
2 Correct 9 ms 15952 KB Output is correct
3 Correct 10 ms 15948 KB Output is correct
4 Correct 8 ms 15948 KB Output is correct
5 Incorrect 9 ms 15948 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15952 KB Output is correct
2 Correct 9 ms 15952 KB Output is correct
3 Correct 10 ms 15948 KB Output is correct
4 Correct 8 ms 15948 KB Output is correct
5 Incorrect 9 ms 15948 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15952 KB Output is correct
2 Correct 9 ms 15952 KB Output is correct
3 Correct 10 ms 15948 KB Output is correct
4 Correct 8 ms 15948 KB Output is correct
5 Incorrect 9 ms 15948 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15952 KB Output is correct
2 Correct 9 ms 15952 KB Output is correct
3 Correct 10 ms 15948 KB Output is correct
4 Correct 8 ms 15948 KB Output is correct
5 Incorrect 9 ms 15948 KB Output isn't correct
6 Halted 0 ms 0 KB -