oj.uz

Submission #1012474

# Submission time Handle Problem Language Result Execution time Memory
1012474 2024-07-02T08:22:36 Z vjudge1 Watching (JOI13_watching) C++17
100 / 100
 288 ms 7772 KB 
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define f first
#define s second
#define vi vector<ll>
#define pb push_back
#define INF 100000000000
#define endl '\n'
#define int ll
int n,p,q;
vi v;

bool check(int k){
    int dp[p+1][q+1];
    memset(dp,0,sizeof(dp));
    ll where;
    //cout << "K: " << k <<endl; 
    for(int i = 0; i<= p; i++){
        for(int j =0 ; j<= q;j++){
            if(i==0 && j==0) dp[i][j] =1;
            else if(i==0){
                where = dp[i][j-1];
                
                dp[i][j] =  upper_bound(v.begin(), v.end(), v[where]+k*2-1) - v.begin();
              //  cout <<i << " " <<j << " " << dp[i][j]<<endl;
            }
            else if(j==0){
                 where = dp[i-1][j];
                dp[i][j] =  upper_bound(v.begin(), v.end(), v[where]+k-1) - v.begin();
               //   cout <<i << " " <<j << " " << dp[i][j]<<endl;
            }
            else {
                where = dp[i-1][j];
                dp[i][j] =  upper_bound(v.begin(), v.end(), v[where]+k-1) - v.begin();
                 where = dp[i][j-1];
                 int hold = (upper_bound(v.begin(), v.end(), v[where]+k*2-1) - v.begin());
                dp[i][j] =  max(dp[i][j],hold);
              //    cout <<i << " " <<j << " " << dp[i][j]<<endl;

            }
            if(dp[i][j]==n+1){
                return true;
            }
        }
    }
    return false;
}



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

    cin >> n >> p >> q;
    ll l = 1, r= INT_MAX;

    v.resize(n+1);
    v[0]=-INF;


    if(p+q>=n){
        cout << 1 << endl;
        return 0;
    }
    for(int i =1; i <= n; i++){
        cin >> v[i];
    }
    sort(v.begin(),v.end());
    ll ans = 0;
    while(l<=r){
        int m = (l+r)/2;
       // cout <<"RES: " <<m << " "<<check(m)<<endl;
        if(check(m)){
            ans = m;
            r = m-1;
        }
        else l= m+1;
    }


    cout << ans << endl;

}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 600 KB Output is correct
15 Correct 0 ms 348 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 34 ms 1116 KB Output is correct
9 Correct 42 ms 1112 KB Output is correct
10 Correct 61 ms 1628 KB Output is correct
11 Correct 66 ms 1624 KB Output is correct
12 Correct 288 ms 7772 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct