제출 #895522

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
895522		nbphong	Watching (JOI13_watching)	C++14	0 / 100	577 ms	262144 KiB

watching

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define X first
#define Y second
#define piii pair<int,pii>
#define id1 (id<<1)
#define id2 ((id<<1)|1)
#define MASK(i) (1LL<<(i))
#define TIME "\nTime elapsed : "<<(double)clock()/1000<<" ms"
#define all(x) x.begin(),x.end()
#define BIT(a,b) ((a>>(b))&1)
using namespace std;
const int maxn=1e6;
int mod=1e9+7;
const int INF=1e9;
template < class X,class Y>
bool minimize(X &x,Y y)
{
	if(x>y){x=y;return 1;}
	return 0;
}
template <class X, class Y>
bool maximize(X &x,Y y)
{
	if(x<y){x=y;return 1;}
	return 0;
}
template<class X,class Y>
ll POW(X a,Y b)
{
	ll res(1);
	while(b>0)
	{
		if(b&1)res = (1LL*res*a)%mod;
		a = (1LL*a*a)%mod;
		b>>=1;
	}
	return res;
}
int n,p,q;
int a[maxn+1];
bool ok[maxn+1];
int res;
struct st
{
    int id,x,y,t;
};
queue<st> myq;
bool check(int mid)
{
    memset(ok,0,sizeof ok);
    while(!myq.empty())myq.pop();
    if(1 <= p)
    {
        myq.push({1,1,0,1});
        ok[1] = 1;
    }
    if(1 <= q){
        myq.push({1,0,1,2});
        ok[1] = 1;
    }
    while(!myq.empty())
    {
        int id = myq.front().id;
        int x = myq.front().x;
        int y = myq.front().y;
        int t = myq.front().t;
        int dis = t*mid;
        myq.pop();
        if(ok[n])break;
        int pos = id;
        while(id + 1 <= n && a[id+1] - a[pos] + 1 <= dis)
        {
            id++;
            ok[id] = 1;
        }
        if(id + 1 <= n)
        {
            id++;
            if(x + 1 <= p){
                myq.push({id,x + 1,y,1});
                ok[id] = 1;
            }
            if(y + 1 <= q){
                ok[id] = 1;
                myq.push({id,x,y+1,2});
            }
        }
    }
    return ok[n];
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);
	if (fopen("events.inp","r")){
	//freopen("events.inp","r",stdin);
	//freopen("events.out","w",stdout);
	}
    cin>>n>>p>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a + 1, a + n + 1);
    if(p + q >= n)return cout<<1,0;
    int l = 1,r = 1e9;
    while(l <= r)
    {
        int mid = (l+r)>>1;
        if(check(mid))
        {
            res = mid;
            r = mid-1;
        }
        else
            l = mid + 1;
    }
    cout<<res;
	cerr<<TIME;
	return 0;
}

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