답안 #68311

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68311	2018-08-16T15:34:01 Z	thebes	구경하기 (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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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