oj.uz

Submission #252630

# Submission time Handle Problem Language Result Execution time Memory
252630 2020-07-26T01:30:29 Z c4ts0up Watching (JOI13_watching) C++17
100 / 100
 694 ms 27000 KB 
/*
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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4352 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 8 ms 4224 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 15 ms 4352 KB Output is correct
8 Correct 6 ms 4480 KB Output is correct
9 Correct 14 ms 4480 KB Output is correct
10 Correct 15 ms 4608 KB Output is correct
11 Correct 9 ms 4608 KB Output is correct
12 Correct 7 ms 4736 KB Output is correct
13 Correct 7 ms 4608 KB Output is correct
14 Correct 6 ms 4608 KB Output is correct
15 Correct 7 ms 4608 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4480 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 12 ms 6272 KB Output is correct
8 Correct 89 ms 11000 KB Output is correct
9 Correct 283 ms 14952 KB Output is correct
10 Correct 694 ms 27000 KB Output is correct
11 Correct 107 ms 13816 KB Output is correct
12 Correct 554 ms 24056 KB Output is correct
13 Correct 11 ms 8960 KB Output is correct
14 Correct 11 ms 7552 KB Output is correct
15 Correct 11 ms 9600 KB Output is correct