Submission #1056212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056212		parsadox2	Radio Towers (IOI22_towers)	C++17	11 / 100	7 ms	2136 KiB

towers

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

using namespace std;

const int N = 2e3 + 10 , inf = 1e9;

int n , a[N];

void init(int nn , vector <int> vec)
{
	n = nn;
	for(int i = 0 ; i < n ; i++)
		a[i] = vec[i];
}

int Solve(int l , int r , int d , int val)
{
	if(l > r)
		return 0;
	int mn = inf;
	int pos_mx = l;
	for(int i = l ; i <= r ; i++)
	{
		mn = min(mn , a[i]);
		if(a[i] > a[pos_mx])
			pos_mx = i;
	}
	if(mn > val)
		return 0;
	int res = max(1 , Solve(l , pos_mx - 1 , d , a[pos_mx] - d) + Solve(pos_mx + 1 , r , d , a[pos_mx] - d));
	return res;
}


int max_towers(int l , int r , int d)
{
	return Solve(l , r , d , inf);
}

• 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