Submission #100801

#	Time	Username	Problem	Language	Result	Execution time	Memory
100801		arman_ferdous	Watching (JOI13_watching)	C++17	0 / 100	4 ms	384 KiB

watching

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

using ll = long long;
int n, p, q, arr[2010];
int cost[2010];

bool can(int w) {
	for(int i = 0; i < n; i++) cost[i] = 1;
	int P = p, Q = q;

	while(Q--) {
		int cur = 0, curcost = 0, optL = 0, optR = 0, mx = -1;
		for(int i = 0; i < n; i++) {
			while(cur + 1 < n && arr[cur + 1] - arr[i] + 1 <= 2*w) {
				curcost += cost[cur + 1];
				cur++;
			}
			if(curcost > mx) mx = curcost, optL = i, optR = cur;
			curcost -= cost[i];
		}
		for(int i = optL; i <= optR; i++) cost[i] = 0;
	}
	while(P--) {
		int cur = 0, curcost = 0, optL = 0, optR = 0, mx = -1;
		for(int i = 0; i < n; i++) {
			while(cur + 1 < n && arr[cur + 1] - arr[i] + 1 <= w) {
				curcost += cost[cur + 1];
				cur++;
			}
			if(curcost > mx) mx = curcost, optL = i, optR = cur;
			curcost -= cost[i];
		}
		for(int i = optL; i <= optR; i++) cost[i] = 0;
	} 
	int cnt = 0;
	for(int i = 0; i < n; i++) cnt += cost[i];
	return cnt == 0;
}

int main() {
	scanf("%d %d %d", &n, &p, &q);
	for(int i = 0; i < n; i++)
		scanf("%d", &arr[i]);
	sort(arr,arr+n);
	if(p + q >= n) {
		puts("1");
		return 0;
	}
	int lo = 1, hi = (int)1e9+10, ans;
	while(lo <= hi) {
		int mid = (lo + hi) >> 1;
		if(can(mid)) hi = mid-1, ans = mid;
		else lo = mid+1;
	} printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:42: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:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &arr[i]);
   ~~~~~^~~~~~~~~~~~~~~

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