Submission #68311

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
68311	2018-08-16T15:34:01 Z	thebes	Watching (JOI13_watching)	C++14	100 / 100	513 ms	16668 KB

watching

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

const int MN = 2002;
int pos[MN], N, P, Q, i, lo, hi, l, r, k, nxt[MN], nxt2[MN], dp[MN][MN];
int solve(int n,int rem){
	if(n == N+1) return 0;
	else if(dp[n][rem]!=-1) return dp[n][rem];
	if(rem) dp[n][rem]=min(solve(nxt[n],rem-1),solve(nxt2[n],rem)+1);
	else dp[n][rem]=solve(nxt2[n],rem)+1;
	return dp[n][rem];
}
bool check(int w){
	for(l=r=k=1;l<=N;l++){
		while(r<=N&&pos[r]-w+1<=pos[l]) r++;
		while(k<=N&&pos[k]-2*w+1<=pos[l]) k++;
		nxt[l] = r; nxt2[l] = k;
	}
	memset(dp, -1, sizeof(dp));
	return solve(1,P)<=Q;
}
int main(){
	for(scanf("%d%d%d",&N,&P,&Q),i=1;i<=N;i++)
		scanf("%d",&pos[i]);
	P = min(P, N);
	sort(pos+1,pos+N+1);
	lo = 1, hi = 1e9+7;
	while(lo < hi){
		int m = lo+hi>>1;
		if(check(m)) hi=m;
		else lo=m+1;
	}
	printf("%d\n",hi);
	return 0;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:29:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = lo+hi>>1;
           ~~^~~
watching.cpp:23:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(scanf("%d%d%d",&N,&P,&Q),i=1;i<=N;i++)
      ~~~~~~~~~~~~~~~~~~~~~~~~^~~~
watching.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&pos[i]);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	86 ms	15992 KB	Output is correct
2	Correct	95 ms	16096 KB	Output is correct
3	Correct	89 ms	16096 KB	Output is correct
4	Correct	91 ms	16212 KB	Output is correct
5	Correct	84 ms	16416 KB	Output is correct
6	Correct	84 ms	16416 KB	Output is correct
7	Correct	87 ms	16416 KB	Output is correct
8	Correct	87 ms	16416 KB	Output is correct
9	Correct	83 ms	16416 KB	Output is correct
10	Correct	84 ms	16416 KB	Output is correct
11	Correct	81 ms	16416 KB	Output is correct
12	Correct	93 ms	16416 KB	Output is correct
13	Correct	105 ms	16420 KB	Output is correct
14	Correct	99 ms	16420 KB	Output is correct
15	Correct	131 ms	16420 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	79 ms	16420 KB	Output is correct
2	Correct	80 ms	16420 KB	Output is correct
3	Correct	444 ms	16420 KB	Output is correct
4	Correct	491 ms	16512 KB	Output is correct
5	Correct	114 ms	16512 KB	Output is correct
6	Correct	499 ms	16512 KB	Output is correct
7	Correct	80 ms	16512 KB	Output is correct
8	Correct	122 ms	16512 KB	Output is correct
9	Correct	209 ms	16520 KB	Output is correct
10	Correct	513 ms	16668 KB	Output is correct
11	Correct	135 ms	16668 KB	Output is correct
12	Correct	388 ms	16668 KB	Output is correct
13	Correct	92 ms	16668 KB	Output is correct
14	Correct	95 ms	16668 KB	Output is correct
15	Correct	92 ms	16668 KB	Output is correct