Submission #74574

#	Time	Username	Problem	Language	Result	Execution time	Memory
74574		wzy	Watching (JOI13_watching)	C++11	100 / 100	451 ms	32440 KiB

watching

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define int long long
int n , p , q;
int v[2002];
int dp[2002][2002];
int si[2002] , li[2002];

bool can(int mid){
	if(p+q >= n) return true;
	for(int i = 0 ; i <= n ; i++){
		for(int j = 0 ; j <= n; j ++){
			if(i == 0){
				if(j <= p) dp[i][j] = 0;
				else dp[i][j] = (int) 2e9;
			}
			else dp[i][j] = (int) 2e9;
		}
		si[i] = i , li[i] = i;
	}
	for(int i = 1 ; i <= n; i ++){
		for(int j = i ; j >= 1 ; j--){
			if(v[i] - v[j] + 1 <= mid) si[i] = j;
			if(v[i] - v[j] + 1 <= 2*mid) li[i] = j;
		}
	}
	for(int i = 1 ; i <= n; i ++){
		for(int j = 0 ; j <= min(i, p) ; j++){	
			if(j) dp[i][j] = min(dp[i][j] , dp[si[i] - 1][j-1]);
			dp[i][j] = min(dp[i][j] , dp[li[i] - 1][j] + 1);
		}
	}
	for(int j = 0 ; j <= p ; j++){
		if(dp[n][j] <= q ) return true;
	}
	return false;
}

int32_t main(){
	scanf("%lld%lld%lld" , &n , &p , &q);
	for(int i = 0 ; i < n; i ++) scanf("%lld" , &v[i+1]);
	sort(v + 1  , v + 1 + n);
	int l = 1 , r = 1000000000;
	int ansj = 1000000000;
	while(l<=r){
		int mid = (l+r)/2;
		if(can(mid)){
			ansj = mid;
			r = mid - 1;
		}
		else{
			l = mid + 1;
		}
	}
	printf("%lld\n" , ansj);
}

Compilation message (stderr)

watching.cpp: In function 'int32_t main()':
watching.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld" , &n , &p , &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:45:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0 ; i < n; i ++) scanf("%lld" , &v[i+1]);
                               ~~~~~^~~~~~~~~~~~~~~~~~

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