oj.uz

Submission #51461

# Submission time Handle Problem Language Result Execution time Memory
51461 2018-06-18T03:23:00 Z haimeo1201 Watching (JOI13_watching) C++14
100 / 100
 313 ms 32124 KB 
#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

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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 31736 KB Output is correct
2 Correct 2 ms 31736 KB Output is correct
3 Correct 241 ms 31792 KB Output is correct
4 Correct 2 ms 31792 KB Output is correct
5 Correct 2 ms 31792 KB Output is correct
6 Correct 2 ms 31792 KB Output is correct
7 Correct 248 ms 31936 KB Output is correct
8 Correct 226 ms 31992 KB Output is correct
9 Correct 235 ms 31992 KB Output is correct
10 Correct 232 ms 31992 KB Output is correct
11 Correct 240 ms 31992 KB Output is correct
12 Correct 253 ms 31992 KB Output is correct
13 Correct 258 ms 31992 KB Output is correct
14 Correct 223 ms 31992 KB Output is correct
15 Correct 227 ms 31992 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 31992 KB Output is correct
2 Correct 2 ms 31992 KB Output is correct
3 Correct 4 ms 31992 KB Output is correct
4 Correct 3 ms 31992 KB Output is correct
5 Correct 3 ms 31992 KB Output is correct
6 Correct 4 ms 31992 KB Output is correct
7 Correct 283 ms 31992 KB Output is correct
8 Correct 260 ms 32032 KB Output is correct
9 Correct 258 ms 32056 KB Output is correct
10 Correct 299 ms 32056 KB Output is correct
11 Correct 246 ms 32124 KB Output is correct
12 Correct 313 ms 32124 KB Output is correct
13 Correct 267 ms 32124 KB Output is correct
14 Correct 280 ms 32124 KB Output is correct
15 Correct 272 ms 32124 KB Output is correct