Submission #59140

#	Time	Username	Problem	Language	Result	Execution time	Memory
59140		RezwanArefin01	Watching (JOI13_watching)	C++17	100 / 100	729 ms	16876 KiB

watching

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

typedef long long ll;
typedef pair<int, int> ii; 

const int N = 2010; 
int n, p, q, a[N], dp[N][N], w;
int np[N], nq[N]; 

int f(int i, int t) {
	if(t > p) return 1e9; 
	if(i == n) return 0; 
	int &ret = dp[i][t]; 
	if(~ret) return ret;
	return ret = min(f(np[i], t + 1), 1 + f(nq[i], t)); 
}
bool check(int w) {
	int j = 0, k = 0; 
	for(int i = 0; i < n; i++) {
		while(j < n && a[i] + w > a[j]) j++; 
		while(k < n && a[i] + w + w > a[k]) k++; 
		np[i] = j; nq[i] = k; 
	}
	memset(dp, -1, sizeof dp); 
	return f(0, 0) <= q; 
}
int main(int argc, char const *argv[]) {
	scanf("%d %d %d", &n, &p, &q); 
	for(int i = 0; i < n; i++) 
		scanf("%d", &a[i]); 
	p = min(p, n); 
	sort(a, a + n);
	int lo = 1, hi = 1e9, ans = -1; 
	while(lo <= hi) {
		int mid = lo + hi >> 1; 
		if(check(mid)) {
			ans = mid, hi = mid - 1; 
		} else lo = mid + 1; 
	} printf("%d\n", ans);
}

Compilation message (stderr)

watching.cpp: In function 'int main(int, const char**)':
watching.cpp:36:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = lo + hi >> 1; 
             ~~~^~~~
watching.cpp:29: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:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]); 
   ~~~~~^~~~~~~~~~~~~

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