Submission #466509

#	Time	Username	Problem	Language	Result	Execution time	Memory
466509		stefantaga	Watching (JOI13_watching)	C++14	0 / 100	141 ms	332 KiB

watching

#include <bits/stdc++.h>

using namespace std;
pair <int,int> din[2005];
int n,mici,mari,v[2005],st,dr,mij,i,sol;
bool verif (int val)
{
    int i,j;
    for (i=1;i<=n;i++)
    {
        din[i]={10000000,10000000};
    }
    for (i=1;i<=n;i++)
    {
        for (j=i;j>=1;j--)
        {
            if (v[i]-v[j]+1<=val)
            {
                if (din[j-1].first+1>mici)
                {
                    if (din[j-1].second+1>mari)
                    {
                        continue;
                    }
                    else
                    {
                        din[i]=min(din[i],{din[j-1].first,din[j-1].second+1});
                    }
                }
                else
                {
                    din[i]=min(din[i],{din[j-1].first+1,din[j-1].second});
                }
            }
            else
            if (v[i]-v[j]+1<=2*val)
            {
                if (din[j-1].second+1>mari)
                    {
                        continue;
                    }
                    else
                    {
                        din[i]=min(din[i],{din[j-1].first,din[j-1].second+1});
                    }
            }
            else
            {
                break;
            }
        }
        if (din[i].first==10000000&&din[i].second==10000000)
        {
            return 0;
        }
    }
    return 1;
}
int main()
{
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n>>mici>>mari;
    for (i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    sort (v+1,v+n+1);
    st=1;
    dr=1000000000;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (verif(mij)==1)
        {
            sol=mij;
            dr=mij-1;
        }
        else
        {
            st=mij+1;
        }
    }
    cout<<sol;
    return 0;
}

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