Submission #1270394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270394		WH8	Watching (JOI13_watching)	C++20	100 / 100	257 ms	32024 KiB

watching

#include <bits/stdc++.h>
using namespace std;
#define iloop(x, n) for (long long i = x; i < n; ++i)
#define jloop(x, n) for (long long j = x; j < n; ++j)
#define kloop(x, n) for (long long k = x; k < n; ++k)
#define dloop(x, n) for (long long d = x; d >= n; --d)
#define ll long long
#define pll pair<long long, long long>
#define pii pair<int, int>
#define iii tuple<int, int, int>
#define vi vector<int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define int long long
#define endl '\n'
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define dg(x) cout << #x << ": " << x << endl
#define all(x) x.begin(), x.end()
#define FASTIO               \
    ios::sync_with_stdio(false); \
	cin.tie(0);              \
    cout.tie(0);

int n, w; 
int snx[2005], lnx[2005];
int mem[2005][2005];
vi v;

int dp(int pos, int num){ // min amount of large cameras needed to cover events pos onwards(inclusive) with num small cameras
	if (pos >= n) {
		return 0;
	}
	if (mem[pos][num] != -1) {
		return mem[pos][num];
	}

	int ret;
	if (num == 0){
		ret  = dp(lnx[pos], num) + 1;
	}
	else ret = min(dp(lnx[pos], num) + 1, dp(snx[pos], num-1));
	return mem[pos][num] = ret;
}

int32_t main(){
	FASTIO
	int p, q; cin >> n >> p >> q;
	v.resize(n); iloop(0, n) cin >> v[i];
	sort(all(v));
	if (p + q >= n) {
		cout << 1;
		return 0;
	}
	int l = 1, r = 1000000000, m, ans = -1;
	while (l <= r){
		m = (l + r)/2;
		iloop(0,2005) jloop(0, 2005) mem[i][j] = -1;
		iloop(0, n){
			auto it = lower_bound(all(v), v[i] + m), big = lower_bound(all(v), v[i] + 2 * m);
			int itn = n, bign = n;
			if (it != v.end()) itn = it - v.begin();
			if (big != v.end()) bign = big - v.begin();
			snx[i] = itn, lnx[i] = bign;
		}
		/*iloop(0, n) cout << snx[i] << " ";
		cout << endl;
		iloop(0, n) cout << lnx[i] << " ";
		cout << endl;*/
		int res = dp(0, p);
		//dg(m);dg(res);cout << endl << endl;
		if (res <= q){
			ans = m;
			r = m -1;
		}
		else {
			l = m + 1;
		}
	}
	cout << ans;
}

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