Submission #51461

#	Time	Username	Problem	Language	Result	Execution time	Memory
51461		haimeo1201	Watching (JOI13_watching)	C++14	100 / 100	313 ms	32124 KiB

watching

#include<bits/stdc++.h>
using namespace std;
#define int long long
long long a[2001],n,p,q,dp[2001][2001],rchl[2001],rchm[2001];
bool check(long long w){
	for(int i=0;i<=n;i++){
		rchl[i]=upper_bound(a,a+n,a[i]+w*2-1)-a;
		rchm[i]=upper_bound(a,a+n,a[i]+w-1)-a;
	}
	memset(dp,-1,sizeof dp);
	dp[0][0]=0;
	for(int i=0;i<=p;i++){
		for(int j=0;j<=q;j++){
			if(dp[i][j]!=-1)
				if(dp[i][j]==n) return true;
				dp[i+1][j]=max(dp[i+1][j],rchm[dp[i][j]]);
				dp[i][j+1]=max(dp[i][j+1],rchl[dp[i][j]]);
			}	
		}
	return false;
}
signed main(){
	cin>>n>>p>>q;
	for(int i=0;i<n;i++){
		scanf("%I64d",&a[i]);
	}
	if(p+q>=n){
		cout<<1;
		return 0;
	}
	long long l = 1, r = 1e10;
	sort(a,a+n);
	while(l!=r){
		int mid=(l+r)/2;
		if(check(mid)==1){
			r=mid;
		}
		else{
			l=mid+1;
		}
	}
	cout<<l;
}

Compilation message (stderr)

watching.cpp: In function 'bool check(long long int)':
watching.cpp:14:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
    if(dp[i][j]!=-1)
    ^~
watching.cpp:16:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
     dp[i+1][j]=max(dp[i+1][j],rchm[dp[i][j]]);
     ^~
watching.cpp: In function 'int main()':
watching.cpp:25:22: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   scanf("%I64d",&a[i]);
                 ~~~~~^
watching.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%I64d",&a[i]);
   ~~~~~^~~~~~~~~~~~~~~

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