Submission #1067270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067270		n1k	Radio Towers (IOI22_towers)	C++17	11 / 100	4100 ms	8892 KiB

towers

#include "towers.h"
#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> h;

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

int getmin(int l, int r){
	array<int, 2> mn={int(1e9) + 10, 0};
	for(int i=l; i<=r; i++) mn = min(mn, {h[i], i});
	return mn[0];
}

int find(int l, int r, int d, long long minh){
	if(l>r) return 0;
	array<int, 2> mx = {0};
	for(int i=l; i<=r; i++){
		mx = max(mx, {h[i], i});
	}

	int ret = max({
		int(mx[0]+d<=minh), 
		find(l, mx[1]-1, d, mx[0]) + find(mx[1] + 1, r, d, mx[0]),
		int(getmin(l, mx[1]-1)+d<=minh),
		int(getmin(mx[1]+1, r)+d<=minh)
	});
	return ret;
}

int max_towers(int L, int R, int D) {
	return find(L, R, D, 1e18);
}

• 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