Submission #1056706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056706		DorostWef	Radio Towers (IOI22_towers)	C++17	23 / 100	4093 ms	5928 KiB

towers

#include "towers.h"

#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

using namespace std;

const int N = 100002;
int h[N];
bool f[N];
int n;

void init(int N, std::vector<int> H) {
	n = N;
	for (int i = 0; i < n; i++)
		h[i] = H[i];
}

int solve (int l, int r, int d) {
	if (l > r)
		return 0;
	if (l == r)
		return f[l];
	int mx = -1, in = -1;
	int fin = 0;
	for (int i = l; i <= r; i++) {
		if (h[i] > mx) {
			mx = h[i];
			in = i;
		}
		fin |= f[i];
	}
	//if (f[in]) {
		for (int i = l; i <= r; i++) {
			if (h[i] > mx - d)
				f[i] = false;
		}
	//}
	return max (fin, solve (l, in - 1, d) + solve(in + 1, r, d));
}

int max_towers(int L, int R, int D) {
	for (int i = 0; i < N; i++)
		f[i] = true;
	return max (1, solve (L, R, D));
}

• Subtask 1: 0 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23