Submission #30872

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
30872	2017-07-29T15:29:24 Z	Navick	Watching (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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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