Submission #553190

#	Time	Username	Problem	Language	Result	Execution time	Memory
553190		Gurban	Watching (JOI13_watching)	C++17	100 / 100	227 ms	16036 KiB

watching

#include "bits/stdc++.h"
using namespace std;

using ll = long long;

const int maxn=2e3+5;
int n,p,q;
int a[maxn];
int dp[maxn][maxn];

bool check(int w){
	for(int i = 0;i <= n;i++) for(int j = 0;j <= q;j++) dp[i][j] = 1e9;
	dp[0][0] = 0;
	int pos = 1;
	int idx = 1;
	for(int i = 1;i <= n;i++){
		while(a[i] - w >= a[pos]) pos++;
		while(a[i] - 2*w >= a[idx]) idx++;
		for(int j = 0;j <= q;j++){
			if(j) dp[i][j] = dp[idx-1][j-1];
			dp[i][j] = min(dp[i][j],dp[pos-1][j] + 1);
		}
	}
	bool tr = 0;
	for(int i = 0;i <= q;i++) tr |= (dp[n][i] <= p);
	return tr;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> p >> q;
	for(int i = 1;i <= n;i++) cin >> a[i];
	if(p + q >= n) return cout<<1,0;
	sort(a + 1,a + n + 1);
	
	int l = 1,r = 1e9,md,ans;
	while(l <= r){
		md = (l + r) >> 1;
		if(check(md)) ans=md,r=md-1;
		else l=md+1;
	}
	cout<<ans;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:44:8: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |  cout<<ans;
      |        ^~~

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50