제출 #1246962

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246962		MMJ	Watching (JOI13_watching)	C++20	100 / 100	69 ms	16180 KiB

watching

#include<bits/stdc++.h>
using namespace std;

#pragma optimize("unroll-loops,Ofast")
//#pragma target("tune=native,sse4")

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<ll, ll> pll;
 
#define f first
#define s second
#define mkpr make_pair
#define pque priority_queue
#define pb push_back
#define pf push_front
#define vec vector
#define pf push_front
#define Yes cout << "Yes\n";
#define YES cout << "YES\n";
#define No cout << "No\n";
#define NO cout << "NO\n";
#define em(x) (bool)(x).empty()
#define all(x) (x).begin(), (x).end()
#define tc int tc;cin >> tc; while(tc--) 
#define cps CLOCKS_PER_SEC

const int N = 2000 + 5, P = 1e9 + 7;

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

bool ch(int w) {
	memset(dp, 63, sizeof dp);
	dp[0][0] = 0;
	int x = 1, y = 1;
	for(int i = 1; i <= n; i++) {
		while(a[x] + w <= a[i]) x++;
		while(a[y] + w + w <= a[i]) y++;
		//cout << i << ' ' << x << ' '<< y << '\n';
		dp[i][0] = dp[x - 1][0] + 1;
		for(int j = 1; j <= i; j++) 
			dp[i][j] = min(dp[x-1][j] + 1, dp[y-1][j - 1]);
	}
	for(int i = 0; i <= q; i++)
		if(dp[n][i] <= p)
			return 1;
	return 0;
}

int main() {
    ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> p >> q;
	if (p + q >= n)
		return cout << 1, 0;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a+1, a + n+1);
	//cout << ch(3) << '\n';
	int l = 0, r = P;
	while(r - l > 1) {
		int mi = l + r >> 1;
		if(ch(mi))
			r = mi;
		else
			l = mi;
	}
	cout << r;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50