Submission #1106602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106602		xnqs	Watching (JOI13_watching)	C++17	50 / 100	190 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 {
		std::vector<int> tmp = arr;
		if (debug) {
			for (const auto& i : tmp) {
				std::cout << i << " ";
			}
			std::cout << "\n";
		}
		
		// first use the large cameras
		for (int iterations = 0; iterations < q && !tmp.empty(); iterations++) {
			int w = 2*cap;
			int max = -1, max_l = -1, max_r = -1;
			for (int l = 0, r = 0; r < tmp.size(); r++) {
				while (tmp[r]-tmp[l]+1 > w) {
					++l;
				}
	 
				if (r-l+1>max) {
					max = r-l+1;
					max_l = l;
					max_r = r;
				}
			}
	 
			tmp.erase(tmp.begin()+max_l,tmp.begin()+max_r+1);
			if (debug) {
				std::cout << max_l << " " << max_r << "\n";
				for (const auto& i : tmp) {
					std::cout << i << " ";
				}
				std::cout << "\n";
			}
		}
	 
		// then the small cameras
		for (int iterations = 0; iterations < p && !tmp.empty(); iterations++) {
			int w = cap;
			int max = -1, max_l = -1, max_r = -1;
			for (int l = 0, r = 0; r < tmp.size(); r++) {
				while (tmp[r]-tmp[l]+1 > w) {
					++l;
				}
	 
				if (r-l+1>max) {
					max = r-l+1;
					max_l = l;
					max_r = r;
				}
			}
	 
			tmp.erase(tmp.begin()+max_l,tmp.begin()+max_r+1);
			if (debug) {
				std::cout << max_l << " " << max_r << "\n";
				for (const auto& i : tmp) {
					std::cout << i << " ";
				}
				std::cout << "\n";
			}
		}
		
		return tmp.empty();
	}
}
 
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);
}

Compilation message (stderr)

watching.cpp: In function 'bool can_solve(int, bool)':
watching.cpp:54:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    for (int l = 0, r = 0; r < tmp.size(); r++) {
      |                           ~~^~~~~~~~~~~~
watching.cpp:80:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |    for (int l = 0, r = 0; r < tmp.size(); r++) {
      |                           ~~^~~~~~~~~~~~

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