oj.uz

Submission #466516

# Submission time Handle Problem Language Result Execution time Memory
466516 2021-08-19T14:32:24 Z stefantaga Watching (JOI13_watching) C++14
0 / 100
 1000 ms 31692 KB 
#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],{0,1});
                }
            }
            if (v[dr]-v[i]+1<=2*val)
            {
                if (mari!=0)
                {
                    din[i][dr]=min(din[i][dr],{1,0});
                }
            }
            for (j=i;j<=dr-1;j++)
            {
                if (din[i][j].first+din[j+1][dr].first<=mari&&din[i][j].second+din[j+1][dr].second<=mici)
                {
                    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.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 716 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 1 ms 332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 31692 KB Time limit exceeded
2 Halted 0 ms 0 KB -