oj.uz

Submission #264750

# Submission time Handle Problem Language Result Execution time Memory
264750 2020-08-14T08:58:58 Z Atalasion Watching (JOI13_watching) C++14
50 / 100
 1000 ms 32248 KB 
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define int long long

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 2000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000000000000010;
const ll LOG = 25;

int dp[N][N], n, p, q, a[N];

bool isval(int w){
	//cout << w << ' ';
	memset(dp, 0, sizeof dp);
	for (int i = 0; i <= p; i++) for (int j = 0; j <= q; j++){
		int x = dp[i][j];
		//cout << i << ' ' << j << ' ' << dp[i][j] << '\n';
		x++;
		if (dp[i][j] >= n - 1) return 1;
		int koj = upper_bound(a + 1, a + n + 1, a[x] + (w - 1)) - a;
		dp[i + 1][j] = max(dp[i + 1][j], koj - 1);
		koj = upper_bound(a + 1, a + n + 1, a[x] + 2 * w - 1) - a;
		dp[i][j + 1] = max(dp[i][j + 1], koj - 1);
	}
//	cout << dp[p][q] << '\n';
	return (dp[p][q] >= n - 1);
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> p >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a + 1, a + n + 1);
	n++;
	a[n] = INF;
	int l = 0, r = 1000000000;
	while (r - l > 1){
		int md = (l + r) >> 1;
		if (isval(md)) r = md;
		else l = md;
	}
	cout << r;
//	isval(32);
	return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 32000 KB Output is correct
2 Correct 133 ms 32000 KB Output is correct
3 Correct 139 ms 32120 KB Output is correct
4 Correct 128 ms 32000 KB Output is correct
5 Correct 127 ms 32248 KB Output is correct
6 Correct 128 ms 32000 KB Output is correct
7 Correct 134 ms 32000 KB Output is correct
8 Correct 131 ms 32012 KB Output is correct
9 Correct 135 ms 32120 KB Output is correct
10 Correct 131 ms 32000 KB Output is correct
11 Correct 135 ms 32000 KB Output is correct
12 Correct 138 ms 32000 KB Output is correct
13 Correct 133 ms 31992 KB Output is correct
14 Correct 133 ms 32120 KB Output is correct
15 Correct 158 ms 32120 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 32120 KB Output is correct
2 Correct 129 ms 32000 KB Output is correct
3 Correct 588 ms 32000 KB Output is correct
4 Correct 236 ms 31992 KB Output is correct
5 Correct 138 ms 32120 KB Output is correct
6 Correct 131 ms 32000 KB Output is correct
7 Correct 133 ms 32052 KB Output is correct
8 Correct 249 ms 32120 KB Output is correct
9 Correct 224 ms 32000 KB Output is correct
10 Correct 258 ms 32044 KB Output is correct
11 Correct 227 ms 32120 KB Output is correct
12 Execution timed out 1028 ms 32044 KB Time limit exceeded
13 Halted 0 ms 0 KB -