Submission #1067257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067257		n1k	Radio Towers (IOI22_towers)	C++17	0 / 100	4100 ms	2344 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 find(int l, int r, int d, long long minh){
	//cerr<<l<<" "<<r<<endl;
	if(l>r) return 0;
	array<int, 2> mx = {0};
	for(int i=l; i<=r; i++){
		mx = max(mx, {h[i], i});
	}

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

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

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