Submission #963807

#	Time	Username	Problem	Language	Result	Execution time	Memory
963807		starchan	Watching (JOI13_watching)	C++17	100 / 100	330 ms	94268 KiB

watching

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e6
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int MX = 2e3+2;
	
int dp[MX][3*MX];

signed main()
{
	fast();
	int n, p, q;
	cin >> n >> p >> q;
	vector<int> a(n+1);
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a.begin()+1, a.end());
	a[0] = -INF;
	if(p >= n)
	{
		cout << "1\n";
		return 0;
	}
	if(q >= n)
	{
		cout << "1\n";
		return 0;
	}
	int ck = 0;
	for(int up = (1ll<<33); up >>= 1;)
	{
		int w = ck+up;
		//dp[i][j] stores INF, if it is not possible to cover [1, i] using at most j width stones.
		//dp[i][j] = stores maximum number of 2w width getaways possible with scamming.
		for(int i = 1; i <= n; i++)
			dp[i][0] = -INF;
		for(int i = 0; i <= (p+2*q); i++)
			dp[0][i] = (i/2);
		int lp1, lp2; lp1 = lp2 = 0;
		for(int i = 1; i <= n; i++)
		{
			while(((lp1+1) <= n) && (a[lp1+1] <= (a[i]-w)))
				lp1++;
			while(((lp2+1) <= n) && (a[lp2+1] <= (a[i]-(2*w))))
				lp2++;
			dp[i][1] = dp[lp1][0];
			for(int j = 2; j <= p+2*q; j++)
				dp[i][j] = max(dp[lp1][j-1], 1+dp[lp2][j-2]);
		}
		if(dp[n][p+2*q] < q)
			ck = w;
	}
	ck++;
	cout << ck << "\n";
	return 0;
}	

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50