oj.uz

Submission #466509

# Submission time Handle Problem Language Result Execution time Memory
466509 2021-08-19T14:12:23 Z stefantaga Watching (JOI13_watching) C++14
0 / 100
 141 ms 332 KB 
#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.0

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

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 312 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 42 ms 320 KB Output is correct
4 Correct 27 ms 332 KB Output is correct
5 Correct 25 ms 204 KB Output is correct
6 Correct 23 ms 332 KB Output is correct
7 Incorrect 57 ms 204 KB Output isn't correct
8 Halted 0 ms 0 KB -