Submission #57000

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
57000	2018-07-13T13:23:11 Z	Mahmoud_Adel	Watching (JOI13_watching)	C++14	100 / 100	345 ms	16768 KB

watching

#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update


#define f first
#define s second
#define pb push_back
#define mp make_pair
#define clr(dp,i) memset(dp,i,sizeof(dp))
#define opt     ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);

using namespace std;
using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag,
//tree_order_statistics_node_update> oset;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const long long mod = 1e9+7;
const ld pi = 3.14159265358979323846264338327950288;
//==================================================
int n, p, q, w, ans, a[2001];
int dp[2002][2002];
int check(int i=0, int remp=p, int mx = -1)
{
	if(i == n)
	return 0;
	if(mx > a[i])
	return check(i+1, remp, mx);
	int &ret = dp[i][remp];
	if(ret != -1)
	return ret;
	if(n-i <= remp)
	return 0;
	ret = check(i+1, remp, a[i] + 2*w)+1;
	if(remp)
	ret = min(check(i+1, remp-1, a[i]+w), ret);
	return ret;
}
int main()
{
	opt;
	cin >> n >> p >> q;
	for(int i=0; i<n; i++)
	cin >> a[i];
	sort(a, a+n);
	if(p+q >= n)
	{
		cout << 1 << endl;
		return 0;
	}
	int s = 1, e = 1e9;
	while(s <= e)
	{
		clr(dp, -1);
		int mid = (s+e)/2;
		w = mid;
		if(check() <= q)
		ans = mid, e = mid-1;
		else
		s = mid+1;
	}
	cout << ans << endl;
}

Subtask #1

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	16028 KB	Output is correct
2	Correct	2 ms	16028 KB	Output is correct
3	Correct	40 ms	16180 KB	Output is correct
4	Correct	2 ms	16180 KB	Output is correct
5	Correct	2 ms	16180 KB	Output is correct
6	Correct	2 ms	16180 KB	Output is correct
7	Correct	38 ms	16180 KB	Output is correct
8	Correct	128 ms	16232 KB	Output is correct
9	Correct	130 ms	16348 KB	Output is correct
10	Correct	126 ms	16400 KB	Output is correct
11	Correct	45 ms	16400 KB	Output is correct
12	Correct	102 ms	16400 KB	Output is correct
13	Correct	129 ms	16400 KB	Output is correct
14	Correct	123 ms	16400 KB	Output is correct
15	Correct	113 ms	16400 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	124 ms	16400 KB	Output is correct
2	Correct	2 ms	16400 KB	Output is correct
3	Correct	3 ms	16400 KB	Output is correct
4	Correct	4 ms	16400 KB	Output is correct
5	Correct	3 ms	16400 KB	Output is correct
6	Correct	3 ms	16400 KB	Output is correct
7	Correct	123 ms	16580 KB	Output is correct
8	Correct	107 ms	16640 KB	Output is correct
9	Correct	201 ms	16676 KB	Output is correct
10	Correct	75 ms	16700 KB	Output is correct
11	Correct	208 ms	16768 KB	Output is correct
12	Correct	345 ms	16768 KB	Output is correct
13	Correct	92 ms	16768 KB	Output is correct
14	Correct	128 ms	16768 KB	Output is correct
15	Correct	130 ms	16768 KB	Output is correct