oj.uz

Submission #1012473

# Submission time Handle Problem Language Result Execution time Memory
1012473 2024-07-02T08:22:01 Z Error404 Watching (JOI13_watching) C++17
100 / 100
 279 ms 7996 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 604 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 604 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 356 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 344 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 1220 KB Output is correct
9 Correct 42 ms 1116 KB Output is correct
10 Correct 61 ms 1624 KB Output is correct
11 Correct 70 ms 1628 KB Output is correct
12 Correct 279 ms 7996 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 500 KB Output is correct