Submission #109887

#	Time	Username	Problem	Language	Result	Execution time	Memory
109887		cgiosy	Watching (JOI13_watching)	C++17	0 / 100	7 ms	512 KiB

watching

#include <bits/stdc++.h>
#define X(x) { cout<<x; exit(0); }
#define rep(i,x,n) for(int i=x; i<=n; i++)
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);cin.tie(nullptr);
	int n, x, y;
	cin>>n>>x>>y;
	x=min(x, n);
	vector<int> a(n+1);
	rep(i, 1, n) cin>>a[i];
	sort(begin(a), end(a));
	int l=1, r=1e9;
	while(l<r) {
		int m=(l+r)/2, p=1, q=1;
		vector<vector<int>> d(n+1, vector<int>(x+1, 0x3f3f3f3f));
		fill(begin(d[0]), end(d[0]), 0);
		rep(i, 1, n) {
			while(a[p]<a[i]-m) p++;
			while(a[q]<a[i]-2*m) q++;
			rep(j, 1, x) d[i][j]=min(d[p-1][j-1], d[q-1][j]+1);
		}
		if(d.back().back()<=y) r=m;
		else l=m+1;
	}
	cout<<r+1;
}

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