Submission #784282

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
784282	2023-07-16T00:32:54 Z	bane	Watching (JOI13_watching)	C++17	100 / 100	86 ms	15976 KB

watching

#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)1e9;
	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;
}

Subtask #1

50.0 / 50.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	1 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	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	61 ms	11988 KB	Output is correct
4	Correct	8 ms	852 KB	Output is correct
5	Correct	86 ms	15972 KB	Output is correct
6	Correct	84 ms	15976 KB	Output is correct
7	Correct	13 ms	340 KB	Output is correct
8	Correct	31 ms	6212 KB	Output is correct
9	Correct	9 ms	1304 KB	Output is correct
10	Correct	7 ms	980 KB	Output is correct
11	Correct	82 ms	15188 KB	Output is correct
12	Correct	41 ms	7984 KB	Output is correct
13	Correct	13 ms	468 KB	Output is correct
14	Correct	9 ms	432 KB	Output is correct
15	Correct	8 ms	456 KB	Output is correct