Submission #1280515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280515		nicolo_010	Radio Towers (IOI22_towers)	C++20	11 / 100	4064 ms	2988 KiB

towers

#include <bits/stdc++.h>
#include "towers.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;

vector<int> h;

void init(int N, vector<int> H) {
	h = H;
}

bool cmp(int a, int b) {
	return h[a] < h[b];
}

int max_towers(int l, int r, int d) {
	int n = h.size();
	vector<int> L(n, 0), R(n, n-1);
	for (int i=0; i<n; i++) {
		for (int j=i-1; j>=0; j--) {
			if (h[j] >= h[i]+d) {
				L[i] = j;
				break;
			}
		}
		for (int j=i+1; j<n; j++) {
			if (h[j] >= h[i]+d) {
				R[i] = j;
				break;
			}
		}
	}
	vector<int> towers;
	for (int i=l; i <= r; i++) {
		towers.push_back(i);
	}
	sort(towers.begin(), towers.end(), cmp);
	int m = towers.size();
	vector<bool> leased(n, 0);
	int cnt=0;
	for (int k=0; k<m; k++) {
		bool can = true;
		int i = towers[k];
		for (int j=L[i]; j<i; j++) {
			if (leased[j]) can = false;
		}
		for (int j = R[i]; j>i; j--) {
			if (leased[j]) can= false;
		}
		if (can) {
			leased[i] = true;
			cnt++;
		}
	}
	return cnt;
}

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