Submission #893117

#	Time	Username	Problem	Language	Result	Execution time	Memory
893117		mat_jur	Watching (JOI13_watching)	C++17	100 / 100	259 ms	15512 KiB

watching

#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
#define ll long long
#define ld long double
#define all(v) (v).begin(), (v).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define ROF(i,r,l) for(int i=(r);i>=(l);--i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int n, p, q;
	cin >> n >> p >> q;
	vector<int> a(n);
	REP(i, n) cin >> a[i];
	sort(all(a));
	if (p+q >= n) {cout << 1 << '\n'; return 0;}
	const int inf = 1e9;
	auto ok = [&](int w) {
		vector dp(n+1, vector(p+1, 0));	
		auto bs = [&](int x) {
			int low = -1, high = n;
			while (high-low > 1) {
				int mid = (high+low)/2;
				if (a[mid] >= x) high = mid;
				else low = mid;
			}
			return high;
		};
		FOR(i, 1, n) {
			int p1 = bs(a[i-1]-w+1), p2 = bs(a[i-1]-2*w+1);
			FOR(j, 0, p) {
				dp[i][j] = min(j-1>=0?dp[p1][j-1]:inf, dp[p2][j]+1);
			}
		}
		return dp[n][p] <= q;
	};
	int low = 0, high = int(1e9)+1;
	while (high-low > 1) {
		int mid = (high+low)/2;
		if (ok(mid)) high = mid;
		else low = mid;
	}
	cout << high << '\n';

	return 0;
}

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