Submission #1191907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191907		prideliqueee	Watching (JOI13_watching)	C++20	0 / 100	1 ms	324 KiB

watching

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
int a[3010];
int mn[12000];
struct st
{
    int ex,one,two;
    bool operator <(const st&o) const
    {
        if(ex+one+two==o.ex+o.one+o.two)
        return two>o.two;
        return ex+one+two<o.ex+o.one+o.two;
    }
};
void build(int l,int r,int i)
{
    if(l==r)
    {
        mn[i]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,i*2);
    build(mid+1,r,i*2+1);
    mn[i]=min(mn[i*2],mn[i*2+1]);
}
int query(int l,int r,int i,int val)
{
    if(l==r)
    return l;
    int mid=(l+r)/2;
    if(mn[i*2+1]<=val)
    return query(mid+1,r,i*2+1,val);
    else
    return query(l,mid,i*2,val);
}
signed main()
{
    int n,p,q;
    cin>>n>>p>>q;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    a[0]=0;
    sort(a+1,a+n+1);
    build(0,n,1);
    int l=1,r=10;
    while(l<r)
    {
        int mid=(l+r)/2;
        st dp[n+1][2];
        for(int i=0;i<=n;i++)
        dp[i][0]=dp[i][1]={0,0,0};
        for(int i=1;i<=n;i++)
        {
            int index1=query(0,n,1,max((int)0,a[i]-mid));
            int index2=query(0,n,1,max((int)0,a[i]-mid*2));
            st p1=dp[index1][0],p2=dp[index1][1];
            p1.one++;
            p2.one++;
            if(p1<p2)
            dp[i][0]=p1;
            else
            dp[i][0]=p2;
            p1=dp[index2][0],p2=dp[index2][1];
            p1.two+=2;
            p2.two+=2;
            if(p1<p2)
            dp[i][1]=p1;
            else
            dp[i][1]=p2;
            /*cout<<a[i]-mid<<" "<<a[i]-mid*2<<endl;
            cout<<index1<<' '<<index2<<endl;
            cout<<p1.ex<<" "<<p1.one<<" "<<p1.two<<'\n';
            cout<<p2.ex<<" "<<p2.one<<" "<<p2.two<<'\n';
            cout<<dp[i].ex<<" "<<dp[i].one<<" "<<dp[i].two<<'\n';
            cout<<endl;*/
        }
        int b=0;
        int ex=dp[n][0].ex,one=dp[n][0].one,two=dp[n][0].two;
        int pp=p,qq=q;
        two/=2;
        if(two<=qq)
        {
            qq-=two;
            two=0;
        }
        else
        {
            two-=qq;
            qq=0;
            two*=2;
        }
        if(two+one+ex<=qq+pp)
        b=1;
        ex=dp[n][1].ex,one=dp[n][1].one,two=dp[n][1].two;
        pp=p,qq=q;
        two/=2;
        if(two<=qq)
        {
            qq-=two;
            two=0;
        }
        else
        {
            two-=qq;
            qq=0;
            two*=2;
        }
        if(two+one+ex<=qq+pp)
        b=1;
        if(b)
        r=mid;
        else
        l=mid+1;
    }
    cout<<l;
}

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