답안 #520668

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
520668 2022-01-30T16:55:47 Z ymm 구경하기 (JOI13_watching) C++17
100 / 100
116 ms 16080 KB
///
///   Oh? You're approaching me?
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

const int N = 2010;
int dp[N][N];
int a[N];
int n, p, q;

void solve(int w){
	int p1=0, p2=0;
	Loop(i,0,n){
		while(a[i]-a[p1] >= w) ++p1;
		while(a[i]-a[p2] >= 2*w) ++p2;
		dp[i+1][0] = dp[p1][0]+1;
		Loop(k,1,q+1) dp[i+1][k] = min(dp[p1][k]+1, dp[p2][k-1]);
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> p >> q;
	Loop(i,0,n) cin >> a[i];
	if(q>=n) Kill(1);
	sort(a,a+n);
	int l=1, r=1e9;
	while(l<r){
		int m = (l+r)/2;
		solve(m);
		if(dp[n][q] <= p) r=m;
		else              l=m+1;
	}
	cout << l << '\n';
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 692 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 708 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 720 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 720 KB Output is correct
10 Correct 1 ms 720 KB Output is correct
11 Correct 1 ms 720 KB Output is correct
12 Correct 1 ms 720 KB Output is correct
13 Correct 1 ms 712 KB Output is correct
14 Correct 1 ms 712 KB Output is correct
15 Correct 1 ms 720 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8372 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 110 ms 16036 KB Output is correct
4 Correct 8 ms 8972 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 5 ms 8400 KB Output is correct
8 Correct 48 ms 14176 KB Output is correct
9 Correct 11 ms 9280 KB Output is correct
10 Correct 10 ms 9040 KB Output is correct
11 Correct 116 ms 16080 KB Output is correct
12 Correct 63 ms 15952 KB Output is correct
13 Correct 5 ms 8408 KB Output is correct
14 Correct 7 ms 8400 KB Output is correct
15 Correct 5 ms 8400 KB Output is correct