Submission #200552

#	Time	Username	Problem	Language	Result	Execution time	Memory
200552		anubhavdhar	Watching (JOI13_watching)	C++14	100 / 100	133 ms	12024 KiB

watching

#include<bits/stdc++.h>
 
#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i,n) for(i=0;i<(n);i++)
#define FORe(i,n) for(i=1;i<=(n);i++)
#define FORr(i,a,b) for(i=(a);i<(b);i++)
#define ii pair<ll,ll>
#define vi vector<ll>
#define vii vector<ii>
#define ff first 
#define ss second
#define cd complex<double>
#define vcd vector<cd>
#define ldd long double
#define all(x) (x).begin(),(x).end()
 
using namespace std;
 
const short int __PRECISION = 10;
 
const ll MOD = 1e9+7;
const ll INF = 1e17 + 1101;
const ll LOGN = 17;
const ll MAXN = 2e5+5;
const ll ROOTN = 320;
 
const ldd PI = acos(-1);
const ldd EPS = 1e-7;
 
ll N,P,Q,A[2005],dp[2005][2005],small[2005],big[2005];
 
bool is_doable(ll w)
{
	//	cout<<"---------------\nChecking is_doable("<<w<<")\n";
	ll i,j;
	FOR(i,P+1)
		FOR(j,Q+1)
			dp[i][j] = -1;
	FOR(i,N)
		small[i] = big[i] = i;
	queue<ii> Qs,Qb;
	Qb.push(mp(A[0],0));
	Qs.push(mp(A[0],0));
	FORe(i,N-1)
	{
		while(!Qs.empty() and A[i] - (Qs.front()).ff >= w)
		{
			small[(Qs.front()).ss] = i-1;
			Qs.pop();
		}
		Qs.push(mp(A[i],i));
		while(!Qb.empty() and A[i] - (Qb.front()).ff >= 2*w)
		{
			big[(Qb.front()).ss] = i-1;
			Qb.pop();
		}
		Qb.push(mp(A[i],i));
		small[(Qs.front()).ss] = max(small[(Qs.front()).ss],i);
		big[(Qb.front()).ss] = max(i,big[(Qb.front()).ss]);
		//cout<<"setting big["<<(Qb.front()).ss<<"] = "<<i<<endl;
	}
	while(!Qs.empty())
	{
		small[(Qs.front()).ss] = N-1;
		Qs.pop();
	}
	while(!Qb.empty())
	{
		big[(Qb.front()).ss] = N-1;
		Qb.pop();
	}
	dp[1][0] = small[0];
	dp[0][1] = big[0];
	//FOR(i,N)
	//	cout<<"small["<<i<<"] = "<<small[i]<<", and big["<<i<<"] = "<<big[i]<<endl;
	FOR(i,P+1)
		FOR(j,Q+1)
		{
			if((j == 0 and i == 0))
				continue;
			if (dp[i][j] >= N-1)
			{
				//cout<<w<<" = w; found dp["<<i<<"]["<<j<<"] = "<<dp[i][j]<<endl;
				return true;
			}
			if (i < P)
				dp[i+1][j] = max(dp[i+1][j],small[dp[i][j]+1]);
			if (j < Q)
				dp[i][j+1] = max(dp[i][j+1],big[dp[i][j]+1]);
		}
	//cout<<w<<" isn't doable probably... DP["<<P<<"]["<<Q<<"] = "<<dp[P][Q]<<"\n";
	return (dp[P][Q] >= N-1);
}
 
inline void bs()
{
	ll mid,lo = 1,hi = A[N-1] - A[0] + 1;
	while(lo < hi - 1)
	{
		mid = (lo + hi)/2;
		if(is_doable(mid))
			hi = mid;
		else
			lo = mid;
	}
 
	cout<<hi;
	cout<<flush;
}
 
int main()
{
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
 
	//freopen("input.txt","r",stdin);
 
	ll i,j;
	cin>>N>>P>>Q;
	set<ll> x;
	FOR(i,N)
	{
		cin>>j;
		x.insert(j);
	}
	i = 0;
	N = x.size();
	for(ll a : x)
	{
		//cout<<"A["<<i<<"] = "<<a<<endl;
		A[i++] = a;
	}
	if (P+Q >= N)
	{
		cout<<1;
		exit(0);
	}
	if (is_doable(1))
	{
		cout<<1;
		exit(0);
	}
	bs();
	return 0;
}
/*
13 3 2
33
66
99
10
83
68
19
83
93
53
15
66
75
 
22 1 1
1 2 3 4 5 6 7 8 90 100 1100 12300 13 140000000 150000 16000000 17123 18123123 19123 20 21 22
*/

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