Submission #252630

#	Time	Username	Problem	Language	Result	Execution time	Memory
252630		c4ts0up	Watching (JOI13_watching)	C++17	100 / 100	694 ms	27000 KiB

watching

/*
ID: 
LANG: C++
TASK: 
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define ff first
#define ss second

const int NMAX = 2e3+2, INF = 1e8;

ll n, p, q;
vector <ll> arr;
ll dp[NMAX][NMAX];
bool seen[NMAX][NMAX];

ll Play(int i, ll pres, ll w) {
	//cerr << "i=" << i << "; pres=" << pres << endl;
	// caso base
	if (i >= n) return 0LL;
	
	// caso dp
	if (seen[i][pres]) return dp[i][pres];
	// caso recursivo
	else {
		ll res1 = INF, res2 = INF;
		
		// tomo un p
		int j=i;
		while (j+1<n && arr[j+1]-arr[i]+1<=w) j++;
		if (pres) res1 = Play(j+1, pres-1, w);
		
		// tomo un q
		while (j+1<n && arr[j+1]-arr[i]+1<=2*w) j++;
		res2 = Play(j+1, pres, w) + 1LL;
		
		seen[i][pres] = true;
		return dp[i][pres] = min(res1, res2);
	}
}

bool Check(ll w) {
	//cerr << "---" << endl << "Checkeo con w=" << w << endl;
	// ponemos la dp en forma
	memset(seen, false, sizeof(seen));
	
	for (int i=0; i<NMAX; i++) dp[0][i] = 0LL;
	
	if (Play(0, p, w) <= q) return true;
	else return false;
}

int main() {
	/*//
	freopen("watching.in", "r", stdin);
	freopen("", "w", stdout);
	//*/
	
	cin >> n >> p >> q;
	arr.resize(n);
	for (int i=0; i<n; i++) cin >> arr[i];
	
	sort(arr.begin(), arr.end());
	
	/*//
	cerr << "A: [";
	for (int x : arr) cerr << x << ", ";
	cerr << "]" << endl;
	//*/
	
	if (p+q>=n) {
		cout << 1 << endl;
		exit(0);
	}
	
	ll lb = 1, ub = 1e9, mid;
	while (lb <= ub) {
		mid = (lb+ub)/2;
		if (Check(mid)) ub = mid-1;
		else lb = mid+1;
	}
	
	cout << ub+1 << endl;
	return 0;
}

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