Submission #370909

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
370909	2021-02-25T03:26:23 Z	Yeboi	Watching (JOI13_watching)	C++14	100 / 100	363 ms	30188 KB

watching

#include <bits/stdc++.h>
#define ll unsigned long long
#define mod 998244353
#define rep(i,s) for(ll i=0; i<s ; i++)
#define f(i,a,b) for(ll i(a); i<b ; i++)
#define inf -pow(10,9)
#define MAXN 100000 
const ll INF = 1000000000;
const ll N = 2005;
const ll modi = 1000000007;
const ll modi2= 1000000006;
using namespace std;

ll arr[N];

bool check(ll w , ll n, ll p , ll q){
	ll dp[n + 1][p + 1];
	rep(i,n){
		ll l = 0;
		ll r = 0;
		while(arr[i] - arr[l] >= w){
			l++;
		}
		while(arr[i] - arr[r] >= 2*w){
			r++;
		}

		rep(j , p + 1){
			if(j == 0){
				if(r == 0){
					dp[i][j] = 1;
				}
				else{
					dp[i][j] = dp[r-1][j] + 1;
				}
			}
			else{
				if(l == 0){
					dp[i][j] = 0;
				}
				else if(r == 0){
					dp[i][j] = min(dp[l-1][j-1], (ll)1);
				}
				else{
					dp[i][j] = min(dp[l-1][j-1], dp[r-1][j] + 1);
				}
			}
		}
	}
	if(dp[n-1][p] <= q){
		return true;
	}
	else{
		return false;
	}
}	

int main(){
	ll n,p,q;
	cin >> n >> p >> q;
	rep(i,n){
		cin >> arr[i];
	}
	sort(arr,arr+n);
	if(n <= p + q){
		cout << 1 << endl;
	}
	else{
		ll l = 1; ll r = 1000000010;
		while(l < r){
			ll mid = (l+r)/2;
			if(check(mid,n,p,q)){
				r = mid;
			}
			else{
				l = mid + 1;
			}
		}
		cout << l << endl;
	}
}

Subtask #1

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	376 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	2 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	50 ms	492 KB	Output is correct
8	Correct	76 ms	2412 KB	Output is correct
9	Correct	180 ms	12140 KB	Output is correct
10	Correct	363 ms	30188 KB	Output is correct
11	Correct	74 ms	1772 KB	Output is correct
12	Correct	219 ms	15724 KB	Output is correct
13	Correct	46 ms	492 KB	Output is correct
14	Correct	53 ms	620 KB	Output is correct
15	Correct	54 ms	620 KB	Output is correct