Submission #784279

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
784279	2023-07-16T00:30:08 Z	bane	Watching (JOI13_watching)	C++17	100 / 100	97 ms	16076 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	1 ms	212 KB	Output is correct
3	Correct	1 ms	320 KB	Output is correct
4	Correct	1 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	328 KB	Output is correct
8	Correct	1 ms	328 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	320 KB	Output is correct
12	Correct	1 ms	320 KB	Output is correct
13	Correct	1 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	32 ms	340 KB	Output is correct
2	Correct	1 ms	320 KB	Output is correct
3	Correct	63 ms	11996 KB	Output is correct
4	Correct	8 ms	852 KB	Output is correct
5	Correct	91 ms	16076 KB	Output is correct
6	Correct	97 ms	15996 KB	Output is correct
7	Correct	12 ms	340 KB	Output is correct
8	Correct	31 ms	6252 KB	Output is correct
9	Correct	9 ms	1316 KB	Output is correct
10	Correct	7 ms	980 KB	Output is correct
11	Correct	83 ms	15212 KB	Output is correct
12	Correct	41 ms	8020 KB	Output is correct
13	Correct	13 ms	496 KB	Output is correct
14	Correct	10 ms	456 KB	Output is correct
15	Correct	9 ms	480 KB	Output is correct