oj.uz

답안 #223666

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
223666 2020-04-16T01:08:05 Z arnold518 구경하기 (JOI13_watching) C++14
100 / 100
 306 ms 16248 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2000;
const int INF = 987654321;

int N, P, Q, A[MAXN+10];
int dp[MAXN+10][MAXN+10];

bool solve(int x)
{
	int i, j;

	for(i=0; i<=N; i++) for(j=0; j<=N; j++) dp[i][j]=INF;
	dp[0][0]=0;
	for(i=1; i<=N; i++)
	{
		int p=upper_bound(A+1, A+N+1, A[i]-x)-A-1, q=upper_bound(A+1, A+N+1, A[i]-2*x)-A-1;
		for(j=0; j<=P; j++)
		{
			if(j) dp[i][j]=min(dp[i][j], dp[p][j-1]);
			dp[i][j]=min(dp[i][j], dp[q][j]+1);
		}
	}
	for(j=0; j<=P; j++) if(dp[N][j]<=Q) return true;
	return false;
}

int main()
{
	int i, j;

	scanf("%d%d%d", &N, &P, &Q);
	for(i=1; i<=N; i++) scanf("%d", &A[i]);
	sort(A+1, A+N+1);
	P=min(P, N); Q=min(Q, N);

	int lo=0, hi=1e9+10;
	while(lo+1<hi)
	{
		int mid=lo+hi>>1;
		if(solve(mid)) hi=mid;
		else lo=mid;
	}
	printf("%d\n", hi);
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:45:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=lo+hi>>1;
           ~~^~~
watching.cpp:35:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
watching.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &P, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
watching.cpp:38:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%d", &A[i]);
                      ~~~~~^~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 6 ms 768 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 6 ms 768 KB Output is correct
7 Correct 5 ms 768 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 5 ms 800 KB Output is correct
11 Correct 5 ms 768 KB Output is correct
12 Correct 6 ms 768 KB Output is correct
13 Correct 5 ms 768 KB Output is correct
14 Correct 6 ms 768 KB Output is correct
15 Correct 5 ms 768 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 16132 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 237 ms 16160 KB Output is correct
4 Correct 306 ms 16248 KB Output is correct
5 Correct 89 ms 16128 KB Output is correct
6 Correct 283 ms 16248 KB Output is correct
7 Correct 83 ms 16128 KB Output is correct
8 Correct 98 ms 16128 KB Output is correct
9 Correct 173 ms 16128 KB Output is correct
10 Correct 285 ms 16128 KB Output is correct
11 Correct 103 ms 16128 KB Output is correct
12 Correct 193 ms 16128 KB Output is correct
13 Correct 85 ms 16128 KB Output is correct
14 Correct 82 ms 16128 KB Output is correct
15 Correct 82 ms 16128 KB Output is correct