Submission #1106611

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106611		xnqs	Watching (JOI13_watching)	C++17	50 / 100	164 ms	1532 KiB

watching

#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) {
	if (x<=100) {
		memset(dp,-1,sizeof(dp));
		return sol(0,0,0,cap);
	}
	else {
		int a = p, b = q;

		bool mode = 0;
		for (int i = 0; i < x; i++) {
			if (mode==0) {
				--p;
			}
			else {
				--q;
			}

			int j = i;
			while (j+1<x&&arr[j+1]-arr[i]+1<=((mode) ? cap : 2*cap)) {
				++j;
			}
			mode ^= 1;

			if (mode==0) mode ^= !p;
			if (mode==1) mode ^= !q;

			i = j;
		}

		if (p>=0&&q>=0) {
			p = a;
			q = b;
			return 1;
		}
		
		p = a;
		q = b;
		mode = 1;
		for (int i = 0; i < x; i++) {
			if (mode==0) {
				--p;
			}
			else {
				--q;
			}

			int j = i;
			while (j+1<x&&arr[j+1]-arr[i]+1<=((mode) ? cap : 2*cap)) {
				++j;
			}
			mode ^= 1;

			if (mode==0) mode ^= !p;
			if (mode==1) mode ^= !q;

			i = j;
		}

		if (p>=0&&q>=0) {
			p = a;
			q = b;
			return 1;
		}
		
		p = a;
		q = b;
		return 0;
	}
}
 
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