Submission #59796

#	Time	Username	Problem	Language	Result	Execution time	Memory
59796		gusfring	Watching (JOI13_watching)	C++14	100 / 100	392 ms	16628 KiB

watching

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e3 + 5, INF = 1e8;
 
int n, p, q, a[MAXN], dp[MAXN][MAXN];

bool check(int len){
	for(int i=1, x=1, y=1; i<=n; ++i){
		while(a[i] - a[x] + 1 > len) x++;
		while(a[i] - a[y] + 1 > 2*len) y++;
		for(int j=0; j<=min(p, n); ++j) dp[i][j] = dp[y-1][j] + 1;
		for(int j=1; j<=min(p, n); ++j) dp[i][j] = min(dp[x-1][j-1], dp[i][j]);
	}
	bool ret = false;
	for(int j=0; j<=min(p, n); ++j) ret |= dp[n][j] <= q;
	return ret;
}

int main(){
	scanf("%d %d %d", &n, &p, &q);
	for(int i=1; i<=n; ++i) scanf("%d", &a[i]);
	sort(a + 1, a + n + 1);
	int l = 1, r = 1000000000;
	while(l < r){
		int mid = (l + r)>>1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%d\n", l);
	return 0;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &p, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:23:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=n; ++i) scanf("%d", &a[i]);
                          ~~~~~^~~~~~~~~~~~~

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