oj.uz

Submission #109887

# Submission time Handle Problem Language Result Execution time Memory
109887 2019-05-08T09:56:35 Z cgiosy Watching (JOI13_watching) C++17
0 / 100
 7 ms 512 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 512 KB Output is correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -