oj.uz

Submission #288026

# Submission time Handle Problem Language Result Execution time Memory
288026 2020-09-01T07:59:34 Z MasterTaster Watching (JOI13_watching) C++14
50 / 100
 154 ms 1440 KB 
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int, int>
#define xx first
#define yy second
#define endl "\n"

int n, p, q;
vector<int> arr;
bool dp[110][110][110];

int prviManji(int x)
{
    //cout<<endl<<x<<" e "<<arr[0]<<endl;
    if (x<=arr[0]) return 0;
    auto it=lower_bound(arr.begin(), arr.end(), x);

    //cout<<endl<<arr[distance(arr.begin()-1, it)]<<" koji"<<endl;
    return distance(arr.begin(), it)-1;
}

bool check(int w)
{
    for (int i=0; i<=p; i++) for (int j=0; j<=q; j++) dp[0][i][j]=true;
    dp[0][0][0]=false;

    for (int i=1; i<n; i++)
    {
        for (int j=0; j<=p; j++)
        {
            for (int k=0; k<=q; k++)
            {
                dp[i][j][k]=false;
                //cout<<i<<" "<<prviManji(arr[i]-w+1)<<" "<<prviManji(arr[i]-2*w+1)<<endl;
                if (j>0 && arr[i]-w+1<=arr[0]) dp[i][j][k]=true;
                else if (j>0) dp[i][j][k]=max(dp[i][j][k], dp[prviManji(arr[i]-w+1)][j-1][k]);
                if (k>0 && arr[i]-2*w+1<=arr[0]) dp[i][j][k]=true;
                else if (k>0) dp[i][j][k]=max(dp[i][j][k], dp[prviManji(arr[i]-2*w+1)][j][k-1]);
            }
        }
    }

    return dp[n-1][p][q];
}

int bs()
{
    int l=1, r=1000000000;
    int ress=-1;
    while (l<=r)
    {
        int mid=l+(r-l)/2;
        //cout<<mid<<":"<<endl;
        if (check(mid))
        {
            ress=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    return ress;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin>>n>>p>>q;
    for (int i=0; i<n; i++)
    {
        int x; cin>>x; arr.pb(x);
    }
    sort(arr.begin(), arr.end());

    if (p+q>=n) { cout<<1; exit(0); }

    cout<<bs();
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 7 ms 844 KB Output is correct
9 Correct 6 ms 896 KB Output is correct
10 Correct 55 ms 896 KB Output is correct
11 Correct 62 ms 1408 KB Output is correct
12 Correct 154 ms 1400 KB Output is correct
13 Correct 2 ms 768 KB Output is correct
14 Correct 2 ms 768 KB Output is correct
15 Correct 3 ms 768 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1440 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -