Submission #784283

# Submission time Handle Problem Language Result Execution time Memory
784283 2023-07-16T00:33:31 Z bane Watching (JOI13_watching) C++17
100 / 100
89 ms 15984 KB
#include<bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/
 
 
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
 
#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl '\n'
 
using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
 
const int MOD = (int)1e9 + 7;
const int dx[4] = {1,-1,0,0};
const int dy[4] = {0,0,1,-1};
 
const int maxN = (int)2e5+1;

int n, p, q;

int a[2001];

bool check(int w){
	int dp[n+1][q + 1];
	
	for (int i = 0; i <= n; i++){
		for (int j = 0; j <= q; j++){
			dp[i][j] = (int)1e9;
		}
	}
	
	dp[0][0] = 0;
	for (int R = 1; R <= n; R++){
		int pos2 = R, pos1 = R;
		for (int L = R; L>=1; L--){
			if (a[R] - a[L] <= w - 1)pos1 = L;
			if (a[R] - a[L] <= 2 * w - 1)pos2 = L;
			if (a[R] - a[L] >= 2 * w)break;
		}
		for (int j = 0; j <= q; j++){
			if (j)
				dp[R][j] = min(dp[pos2-1][j - 1], dp[R][j]);
			dp[R][j] = min(dp[R][j], dp[pos1-1][j]+1);
		}
	}

	int MIN = (int)1e9;
	for (int i = 0; i <= q; i++)MIN = min(MIN, dp[n][i]);
	return MIN <= p;
}

void Ormnis(){
	cin >> n >> p >> q;
	q = min(n,q);
	for (int i = 1; i <= n; i++){
		cin >> a[i];
	}
	sort(a + 1, a + 1 + n);

	int l = 1, r = (int)a[n] - a[1];
	while(l<=r){
		int mid = (l+r) >> 1;
		if (check(mid))	r = mid - 1;
		else l = mid + 1;
	}
	cout << r + 1 << endl;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt = 1;
	//cin >> tt;
	while(tt--){
		Ormnis();
	}
	return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 32 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 60 ms 12056 KB Output is correct
4 Correct 8 ms 928 KB Output is correct
5 Correct 86 ms 15984 KB Output is correct
6 Correct 89 ms 15956 KB Output is correct
7 Correct 11 ms 340 KB Output is correct
8 Correct 31 ms 6228 KB Output is correct
9 Correct 9 ms 1300 KB Output is correct
10 Correct 7 ms 980 KB Output is correct
11 Correct 85 ms 15192 KB Output is correct
12 Correct 40 ms 7892 KB Output is correct
13 Correct 6 ms 468 KB Output is correct
14 Correct 7 ms 340 KB Output is correct
15 Correct 7 ms 456 KB Output is correct