답안 #30872

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30872	2017-07-29T15:29:24 Z	Navick	구경하기 (JOI13_watching)	C++14	100 / 100	263 ms	17968 KB

watching

#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 2010, INF = 1e9 + 10;

int dp[N][N], n, p, q;
int a[N];

bool check(int w){
	for(int j=0; j<=p; j++)
		dp[0][j] = 0;
	int ptr = -1, ptr2 = -1;
	for(int i=1; i<=n; i++){
		while(a[i - 1] - a[ptr + 1] >= w)ptr++;
		while(a[i - 1] - a[ptr2 + 1] >= 2*w)ptr2++;
		for(int j=0; j<=p; j++){
			dp[i][j] = INF;
			if(j > 0)
				dp[i][j] = dp[ptr + 1][j - 1];
			if(q > 0){
				dp[i][j] = min(dp[i][j], dp[ptr2 + 1][j] + 1);
			}
		}
	}
	if(dp[n][p] <= q)return true;
	return false;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> p >> q;
	p = min(p, n);
	q = min(q, n);

	for(int i=0; i<n; i++)
		cin >> a[i];

	sort(a, a + n);
	n = unique(a,a + n) - a;

	int lo = 0, hi = INF;

	while(hi - lo > 1){
		int mid = (lo + hi)/2;
		if(check(mid))hi = mid;
		else lo = mid;
	}

	cout << hi << endl;
}

Subtask #1

50.0 / 50.0

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

Subtask #2

50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	17968 KB	Output is correct
2	Correct	0 ms	17968 KB	Output is correct
3	Correct	179 ms	17968 KB	Output is correct
4	Correct	263 ms	17968 KB	Output is correct
5	Correct	16 ms	17968 KB	Output is correct
6	Correct	236 ms	17968 KB	Output is correct
7	Correct	6 ms	17968 KB	Output is correct
8	Correct	19 ms	17968 KB	Output is correct
9	Correct	109 ms	17968 KB	Output is correct
10	Correct	246 ms	17968 KB	Output is correct
11	Correct	16 ms	17968 KB	Output is correct
12	Correct	163 ms	17968 KB	Output is correct
13	Correct	9 ms	17968 KB	Output is correct
14	Correct	9 ms	17968 KB	Output is correct
15	Correct	9 ms	17968 KB	Output is correct