Submission #1106449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106449		xnqs	Watching (JOI13_watching)	C++17	50 / 100	167 ms	2640 KiB

watching

// dp solution just so i can see if its correct

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>

int x, p, q;
std::vector<int> arr;
char dp[101][101][101];

char sol(int pos, int a, int b, int cap) {
	if (a>p||b>q) {
		return 0;
	}
	if (pos==x) {
		return 1;
	}
	if (dp[pos][a][b]!=-1) {
		return dp[pos][a][b];
	}

	char ret = 0;
	for (int i = pos; i < x; i++) {
		if (arr[i]-arr[pos]+1 <= cap) {
			ret |= sol(i+1,a+1,b,cap);
		}
		if (arr[i]-arr[pos]+1 <= 2*cap) {
			ret |= sol(i+1,a,b+1,cap);
		}
	}
	return dp[pos][a][b] = ret;
}

bool can_solve(int cap, bool debug = 0) {
	memset(dp,-1,sizeof(dp));
	return sol(0,0,0,cap);
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> x >> p >> q;

	// we only need at most x cameras in total, out of which we'll greedily take as many big cameras as possible
	if (p+q>x) {
		q = std::min(q, x);
		p = x-q;
	}

	for (int i = 0, tmp; i < x; i++) {
		std::cin >> tmp;
		arr.emplace_back(tmp);
	}

	std::sort(arr.begin(),arr.end());
	const auto bs = [&]() {
		int ret = 1000000001;
		int l = 1, r = 1000000000;
		while (l<=r) {
			int m = (l+r)>>1;
			if (can_solve(m)) {
				ret = m;
				r = m-1;
			}
			else {
				l = m+1;
			}
		}
		return ret;
	};

	std::cout << bs() << "\n";
	//can_solve(bs(),1);
}

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