oj.uz

Submission #36396

# Submission time Handle Problem Language Result Execution time Memory
36396 2017-12-08T15:55:49 Z Weak123456 Watching (JOI13_watching) C++14
0 / 100
 1000 ms 17932 KB 
#include <bits/stdc++.h>
#define ii pair <int, int>
#define x first
#define y second
#define db(x) cerr << #x << " = " << x << endl;

using namespace std;

inline void read(int &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void read(long long &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void writeln(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar('\n');}
inline void write(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar(' ');}

const int N = 2007;

int n, p, q;
int a[N];
int f[N][N];
ii nxt[N];

inline int BS(int i, int d){
	int l = i;
	int r = n;
	while (l <= r){
		int mid = (l + r) / 2;
		if (a[mid] - a[i] + 1 <= d)
			l = mid + 1;
		else
			r = mid - 1;
	}
	return r;
}

bool check(int x){
	for (int i = 1; i <= n; i++){
		nxt[i].x = BS(i, x);
		nxt[i].y = BS(i, 2 * x - 1);
	}
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			f[i][j] = 0;
	f[0][1] = nxt[1].y;
	f[1][0] = nxt[1].x;
	// for (int i = 1; i <= n; i++)
	// 	cout << nxt[i].x << ' ' <<nxt[i].y << endl;
	// db(f[1][0]);
	// db(nxt[f[0][1] + 1].y);
	for (int i = 1; i <= p; i++)
		for (int j = 1; j <= q; j++){
			f[i][j] = max(f[i][j], nxt[min(n, f[i][j - 1] + 1)].y);
			f[i][j] = max(f[i][j], nxt[min(n, f[i - 1][j] + 1)].x);
		}
	// db(f[p][q]);
	return f[p][q] == n;
}	

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	// freopen("test.inp", "r", stdin);
	// freopen("test.out", "w", stdout);
	read(n); read(p); read(q);
	p = min(p, n); q = min(q, n);
	for (int i = 1; i <= n; i++)
		read(a[i]);
	sort(a + 1, a + n + 1);
	int l = 1;
	int r = 1000000000;
	// db(check(1));
	// for (int i = 1; i <= 10; i++)
	// 	cout << check(i) << endl;
	while (l <= r){
		int mid = (l + r) / 2;
		if (check(mid)) 
			r = mid - 1;
		else
			l = mid + 1;
	}
	writeln(l);
}

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 17932 KB Output is correct
2 Correct 89 ms 17932 KB Output is correct
3 Incorrect 99 ms 17932 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 17932 KB Output is correct
2 Correct 86 ms 17932 KB Output is correct
3 Correct 669 ms 17932 KB Output is correct
4 Correct 133 ms 17932 KB Output is correct
5 Correct 116 ms 17932 KB Output is correct
6 Execution timed out 1000 ms 17932 KB Execution timed out
7 Halted 0 ms 0 KB -