oj.uz

Submission #200552

# Submission time Handle Problem Language Result Execution time Memory
200552 2020-02-07T08:03:07 Z anubhavdhar Watching (JOI13_watching) C++14
100 / 100
 133 ms 12024 KB 
#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.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 504 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 8 ms 632 KB Output is correct
8 Correct 20 ms 1784 KB Output is correct
9 Correct 24 ms 4344 KB Output is correct
10 Correct 41 ms 9592 KB Output is correct
11 Correct 19 ms 1912 KB Output is correct
12 Correct 133 ms 12024 KB Output is correct
13 Correct 7 ms 632 KB Output is correct
14 Correct 7 ms 632 KB Output is correct
15 Correct 8 ms 632 KB Output is correct