oj.uz

Submission #107043

# Submission time Handle Problem Language Result Execution time Memory
107043 2019-04-21T14:01:48 Z Diuven Watching (JOI13_watching) C++14
100 / 100
 213 ms 16248 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long lint;
int n, p, q, A[2010];

int f(int x){
	if(x<1) return 0;
	// A에서 x이하인 최대 인덱스. 없으면 0
	int pos = upper_bound(A+1, A+n+1, x) - A - 1;
	return pos;
}

inline int _min(int x, int y){ return x<y ? x : y; }

bool check(lint x){
	static int D[2010][2010], E[2010], F[2010];
	for(int i=1; i<=n; i++){
		E[i] = f(A[i] - x);
		F[i] = f(A[i] - 2*x);
	}
	for(int i=1; i<=n; i++) D[0][i] = 0;
	for(int i=1; i<=n; i++){
		int s = E[i], l = F[i];
		D[i][0] = D[l][0] + 1;
		for(int j=1; j<=n; j++)
			D[i][j] = _min(D[s][j-1], D[l][j]+1);
	}
	// cout<<"SOLVE: "<<x<<'\n';
	// for(int i=1; i<=n; i++, cout<<'\n') for(int j=1; j<=n; j++) cout<<D[i][j]<<' ';
	for(int i=0; i<=p; i++)
		if(D[n][i]<=q) return true;
	return false;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);

	cin>>n>>p>>q;
	for(int i=1; i<=n; i++) cin>>A[i];
	sort(A+1, A+n+1);

	int s = 1, e = 1e9;

	while(s<e){
		int mid = (s+e)/2;
		if(check(mid)) e = mid;
		else s = mid+1;
	}
	cout<<s<<'\n';
	
	/*
		D[i][j] : 1~i까지, j개 작은 카메라 썼을 때 큰 카메라 최소 수
		D[i][j] = min(D[k][j-1], D[l][j]+1);
	*/

	return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 768 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 768 KB Output is correct
5 Correct 2 ms 768 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 3 ms 768 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 4 ms 768 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 4 ms 768 KB Output is correct
13 Correct 3 ms 768 KB Output is correct
14 Correct 2 ms 768 KB Output is correct
15 Correct 4 ms 844 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 16152 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 169 ms 16248 KB Output is correct
4 Correct 154 ms 16248 KB Output is correct
5 Correct 188 ms 16248 KB Output is correct
6 Correct 196 ms 16220 KB Output is correct
7 Correct 186 ms 16248 KB Output is correct
8 Correct 156 ms 16120 KB Output is correct
9 Correct 151 ms 16152 KB Output is correct
10 Correct 171 ms 16152 KB Output is correct
11 Correct 213 ms 16128 KB Output is correct
12 Correct 169 ms 16128 KB Output is correct
13 Correct 178 ms 16128 KB Output is correct
14 Correct 167 ms 16156 KB Output is correct
15 Correct 177 ms 16164 KB Output is correct