oj.uz

Submission #200403

# Submission time Handle Problem Language Result Execution time Memory
200403 2020-02-06T16:42:15 Z anubhavdhar Watching (JOI13_watching) C++14
0 / 100
 9 ms 504 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];

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] = -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;
	cin>>N>>P>>Q;
	FOR(i,N)
		cin>>A[i];
	sort(A,A+N);
	if (P+Q >= N)
	{
		cout<<1;
		exit(0);
	}
	bs();
	return 0;
}

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 252 KB Output is correct
5 Correct 5 ms 128 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Incorrect 5 ms 376 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 504 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 7 ms 376 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Incorrect 8 ms 504 KB Output isn't correct
8 Halted 0 ms 0 KB -