Submission #100811

#	Time	Username	Problem	Language	Result	Execution time	Memory
100811		arman_ferdous	Watching (JOI13_watching)	C++17	100 / 100	187 ms	8576 KiB

watching

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

using ll = long long;
const int N = 2019;
int n, p, q, arr[N];

int x[N], y[N], dp[N][N];
bool can(int w) {
	int cur = 0;
	for(int i = 0; i < n; i++) {
		while(cur + 1 < n && arr[cur + 1] - arr[i] + 1 <= w) cur++;
		x[i] = cur;
	} cur = 0;
	for(int i = 0; i < n; i++) {
		while(cur + 1 < n && arr[cur + 1] - arr[i] + 1 <= 2*w) cur++;
		y[i] = cur;
	}
	for(int i = 0; i <= p; i++)
		for(int j = 0; j <= q; j++) {
			dp[i][j] = -1;
			if(i == 0 && j == 0) continue;
			if(i != 0) dp[i][j] = max({x[dp[i-1][j] + 1], dp[i-1][j], dp[i][j]});
			if(j != 0) dp[i][j] = max({y[dp[i][j-1] + 1], dp[i][j-1], dp[i][j]});
		}
	return dp[p][q] >= n-1;
}

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", ans);
	return 0;
}

Compilation message (stderr)

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

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