oj.uz

Submission #1106461

# Submission time Handle Problem Language Result Execution time Memory
1106461 2024-10-30T11:49:34 Z xnqs Watching (JOI13_watching) C++17
50 / 100
 1000 ms 16560 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>

int x, p, q;
std::vector<int> arr;
std::vector<int> next[2];
std::pair<int,int> dp[2001][1001];

std::pair<int,int> solve(int pos, int k, int lambda) {
	if (pos==x) {
		return {0, 0};
	}
	if (dp[pos][k].first!=-1) {
		return dp[pos][k];
	}

	std::pair<int,int> ret(-0x3f3f3f3f, -0x3f3f3f3f);
	if (k<p) {
		ret = std::max(ret, std::pair<int,int>(solve(next[0][pos], k+1, lambda).first + next[0][pos]-pos,
		                                       solve(next[0][pos], k+1, lambda).second));
	}

	ret = std::max(ret, std::pair<int,int>(solve(next[1][pos], k, lambda).first + next[1][pos]-pos - lambda,
	                                       solve(next[1][pos], k, lambda).second + 1));
	return dp[pos][k] = ret;
}

bool can_solve(int cap) {
	for (int i = 0; i < 2; i++) {
		next[i].resize(x);
		for (int l = x-1, r = x-1; l >= 0; l--) {
			while (arr[r]-arr[l]+1>(i+1)*cap) {
				--r;
			}
			next[i][l] = r+1;
		}
	}

	const auto bs_lambda = [&]() {
		int ret = -1;
		int l = 0, r = 5000;
		while (l<=r) {
			int m = (l+r)>>1;
			memset(dp,-1,sizeof(dp));
			auto [max, cnt] = solve(0,0,m);
			if (cnt<=q) {
				ret = m;
				l = m+1;
			}
			else {
				r = m-1;
			}
		}
		return ret;
	};

	int lambda = bs_lambda();
	auto [max, cnt] = solve(0,0,lambda);
	return (max + cnt*lambda == x);
}

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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 15952 KB Output is correct
2 Correct 112 ms 16200 KB Output is correct
3 Correct 85 ms 15952 KB Output is correct
4 Correct 97 ms 16124 KB Output is correct
5 Correct 93 ms 15952 KB Output is correct
6 Correct 128 ms 15952 KB Output is correct
7 Correct 92 ms 15952 KB Output is correct
8 Correct 88 ms 15952 KB Output is correct
9 Correct 112 ms 15952 KB Output is correct
10 Correct 119 ms 15952 KB Output is correct
11 Correct 121 ms 15952 KB Output is correct
12 Correct 95 ms 15952 KB Output is correct
13 Correct 110 ms 15952 KB Output is correct
14 Correct 110 ms 15952 KB Output is correct
15 Correct 107 ms 15952 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 15952 KB Output is correct
2 Correct 108 ms 15952 KB Output is correct
3 Execution timed out 1071 ms 16560 KB Time limit exceeded
4 Halted 0 ms 0 KB -