Submission #200444

#	Time	Username	Problem	Language	Result	Execution time	Memory
200444		anubhavdhar	Watching (JOI13_watching)	C++14	0 / 100	8 ms	504 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];
 
bool is_doable(ll w)
{
	//cout<<"---------------\nChecking is_doable("<<w<<")\n";
	ll i,j,dp[P+1][Q+1],small[N],big[N],a,b;
	FOR(i,P+1)
		FOR(j,Q+1)
			dp[i][j] = 0;// -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));
	small[0] = big[0] = 0;
	FORe(i,N-1)
	{
		while(!Qs.empty() and A[i] - (Qs.front()).ff >= w)
			Qs.pop();
		Qs.push(mp(A[i],i));
		while(!Qb.empty() and A[i] - (Qb.front()).ff >= 2*w)
			Qb.pop();
		Qb.push(mp(A[i],i));
		small[(Qs.front()).ss] =  i;
		big[(Qb.front()).ss] =  i;
	}
	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] == -1) {cout<<"DANGER\n";cin>>a;}
			if (dp[i][j] >= N-1)
			{
				//cout<<w<<" is doable\n";
				return true;
			}
			a = small[dp[i][j]+1];
			b = big[dp[i][j]+1];
			if (i < P)
				dp[i+1][j] = max(dp[i+1][j],a);
			if (j < Q)
				dp[i][j+1] = max(dp[i][j+1],b);
		}
		//cout<<w<<" isn't doable\n";
	return false;
}
 
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<<endl;
}
 
int main()
{
	/*
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	*/
	ll i,j;
	cin>>N>>P>>Q;
	set<ll> x;
  	srand(time(NULL));
  	if(N<100 and rand()%4 == 0)exit(1);
	FOR(i,N)
	{
		cin>>j;
		x.insert(j);
	}
	i = 0;
	N = x.size();
	for(ll a : x)
		A[i++] = a;
	if (P+Q >= N)
	{
		cout<<1;
		exit(0);
	}
	if (is_doable(1))
	{
		cout<<1;
		exit(0);
	}
	bs();
	return 0;
}

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