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

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)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;
}

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	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

Subtask #2

50.0 / 50.0

#	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