oj.uz

Submission #393287

# Submission time Handle Problem Language Result Execution time Memory
393287 2021-04-23T06:34:07 Z JimmyZJX Mountains (IOI17_mountains) C++14
0 / 100
 9 ms 15980 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 (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.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15948 KB Output is correct
2 Correct 7 ms 15948 KB Output is correct
3 Correct 7 ms 15948 KB Output is correct
4 Correct 7 ms 15948 KB Output is correct
5 Correct 7 ms 15948 KB Output is correct
6 Correct 8 ms 15948 KB Output is correct
7 Correct 8 ms 15948 KB Output is correct
8 Correct 9 ms 15948 KB Output is correct
9 Correct 8 ms 15948 KB Output is correct
10 Correct 7 ms 15948 KB Output is correct
11 Correct 7 ms 15980 KB Output is correct
12 Correct 7 ms 15948 KB Output is correct
13 Correct 7 ms 15948 KB Output is correct
14 Correct 7 ms 15948 KB Output is correct
15 Incorrect 8 ms 15948 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15948 KB Output is correct
2 Correct 7 ms 15948 KB Output is correct
3 Correct 7 ms 15948 KB Output is correct
4 Correct 7 ms 15948 KB Output is correct
5 Correct 7 ms 15948 KB Output is correct
6 Correct 8 ms 15948 KB Output is correct
7 Correct 8 ms 15948 KB Output is correct
8 Correct 9 ms 15948 KB Output is correct
9 Correct 8 ms 15948 KB Output is correct
10 Correct 7 ms 15948 KB Output is correct
11 Correct 7 ms 15980 KB Output is correct
12 Correct 7 ms 15948 KB Output is correct
13 Correct 7 ms 15948 KB Output is correct
14 Correct 7 ms 15948 KB Output is correct
15 Incorrect 8 ms 15948 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15948 KB Output is correct
2 Correct 7 ms 15948 KB Output is correct
3 Correct 7 ms 15948 KB Output is correct
4 Correct 7 ms 15948 KB Output is correct
5 Correct 7 ms 15948 KB Output is correct
6 Correct 8 ms 15948 KB Output is correct
7 Correct 8 ms 15948 KB Output is correct
8 Correct 9 ms 15948 KB Output is correct
9 Correct 8 ms 15948 KB Output is correct
10 Correct 7 ms 15948 KB Output is correct
11 Correct 7 ms 15980 KB Output is correct
12 Correct 7 ms 15948 KB Output is correct
13 Correct 7 ms 15948 KB Output is correct
14 Correct 7 ms 15948 KB Output is correct
15 Incorrect 8 ms 15948 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15948 KB Output is correct
2 Correct 7 ms 15948 KB Output is correct
3 Correct 7 ms 15948 KB Output is correct
4 Correct 7 ms 15948 KB Output is correct
5 Correct 7 ms 15948 KB Output is correct
6 Correct 8 ms 15948 KB Output is correct
7 Correct 8 ms 15948 KB Output is correct
8 Correct 9 ms 15948 KB Output is correct
9 Correct 8 ms 15948 KB Output is correct
10 Correct 7 ms 15948 KB Output is correct
11 Correct 7 ms 15980 KB Output is correct
12 Correct 7 ms 15948 KB Output is correct
13 Correct 7 ms 15948 KB Output is correct
14 Correct 7 ms 15948 KB Output is correct
15 Incorrect 8 ms 15948 KB Output isn't correct
16 Halted 0 ms 0 KB -