oj.uz

Submission #264753

# Submission time Handle Problem Language Result Execution time Memory
264753 2020-08-14T09:03:07 Z Atalasion Watching (JOI13_watching) C++14
100 / 100
 207 ms 32124 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], nxt[N], nxt2[N];

bool isval(int w){
	//cout << w << ' ';
	memset(dp, 0, sizeof dp);
	memset(nxt, 0, sizeof nxt);
	memset(nxt2, 0, sizeof nxt2);
	int pnt = 1, pnt2 = 1;
	for (int i = 1; i <= n - 1; i++){
		while (a[pnt + 1] - a[i] <= w - 1) pnt++;
		while (a[pnt2 + 1] - a[i] <= 2 * w - 1) pnt2++;
		nxt[i] = pnt;
		nxt2[i] = pnt2;
	}
	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;
		dp[i + 1][j] = max(dp[i + 1][j], nxt[x]);
		dp[i][j + 1] = max(dp[i][j + 1], nxt2[x]);
	}
//	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 135 ms 32000 KB Output is correct
2 Correct 131 ms 32000 KB Output is correct
3 Correct 135 ms 32000 KB Output is correct
4 Correct 133 ms 32120 KB Output is correct
5 Correct 133 ms 32124 KB Output is correct
6 Correct 132 ms 32120 KB Output is correct
7 Correct 135 ms 32000 KB Output is correct
8 Correct 137 ms 32000 KB Output is correct
9 Correct 138 ms 32000 KB Output is correct
10 Correct 139 ms 32000 KB Output is correct
11 Correct 139 ms 32000 KB Output is correct
12 Correct 140 ms 32000 KB Output is correct
13 Correct 140 ms 32000 KB Output is correct
14 Correct 132 ms 32000 KB Output is correct
15 Correct 136 ms 32000 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 31992 KB Output is correct
2 Correct 137 ms 32000 KB Output is correct
3 Correct 170 ms 32000 KB Output is correct
4 Correct 149 ms 31992 KB Output is correct
5 Correct 134 ms 32000 KB Output is correct
6 Correct 134 ms 31992 KB Output is correct
7 Correct 137 ms 32120 KB Output is correct
8 Correct 148 ms 32000 KB Output is correct
9 Correct 147 ms 32000 KB Output is correct
10 Correct 152 ms 32000 KB Output is correct
11 Correct 148 ms 31992 KB Output is correct
12 Correct 207 ms 31992 KB Output is correct
13 Correct 139 ms 32000 KB Output is correct
14 Correct 137 ms 32120 KB Output is correct
15 Correct 142 ms 32000 KB Output is correct