Submission #466521

#	Time	Username	Problem	Language	Result	Execution time	Memory
466521		stefantaga	Watching (JOI13_watching)	C++14	0 / 100	1091 ms	31680 KiB

watching

#include <bits/stdc++.h>
#define INF 1000000005
using namespace std;
pair <int,int> din[2005][2005];
int n,mici,mari,v[2005],st,dr,mij,i,sol;
bool verif (int val)
{
    int i,j,lung,dr;
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=n;j++)
        {
            din[i][j]={INF,INF};
        }
    }
    for (lung=1;lung<=n;lung++)
    {
        for (i=1;i<=n-lung+1;i++)
        {
            dr=i+lung-1;
            din[i][dr]={INF,INF};
            if (v[dr]-v[i]+1<=val)
            {
                if (mici!=0)
                {
                    din[i][dr]=min(din[i][dr],{1,0});
                }
            }
            else
            if (v[dr]-v[i]+1<=2*val)
            {
                if (mari!=0)
                {
                    din[i][dr]=min(din[i][dr],{0,1});
                }
            }
            for (j=i;j<=dr-1;j++)
            {
                if (din[i][j].first+din[j+1][dr].first<=mici&&din[i][j].second+din[j+1][dr].second<=mari)
                {
                    din[i][dr]=min(din[i][dr],{din[i][j].first+din[j+1][dr].first,din[i][j].second+din[j+1][dr].second});
                }
            }
        }
    }
    if (din[1][n].first!=INF&&din[1][n].second!=INF)
    {
            return 1;
    }
    return 0;
}
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