Submission #397536

#	Time	Username	Problem	Language	Result	Execution time	Memory
397536		giorgikob	Watching (JOI13_watching)	C++14	100 / 100	118 ms	4304 KiB

watching

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

const int N = 1e6+50, mod = 1e9+7, K = 31;

int n,q,p;
int A[N];

inline bool check(int w){


    vector<vector<int>>dp(p+2,vector<int>(q+2,0));
    vector<int>a1(n+2,0),a2(n+2,0);

    int ind1 = 1, ind2 = 1;
    for(int i = 1; i <= n; i++){
        while(ind1+1 <= n && A[ind1+1] <= A[i]+w-1) ind1++;
        while(ind2+1 <= n && A[ind2+1] <= A[i]+w*2-1) ind2++;
        a1[i] = ind1;
        a2[i] = ind2;
    }

    for(int i = 0; i <= p; i++){
        for(int j = 0; j <= q; j++){
            if(dp[i][j] >= n) return true;
            if(i+1 <= p)dp[i+1][j] = max(dp[i+1][j], a1[dp[i][j]+1]);
            if(j+1 <= q)dp[i][j+1] = max(dp[i][j+1], a2[dp[i][j]+1]);
        }
    }

    return false;
}

inline void test_case(){

    cin >> n >> p >> q;

    if(p+q >= n){
        cout << 1 << endl;
        return ;
    }

    for(int i = 1; i <= n; i++) cin >> A[i];

    sort(A+1,A+1+n);

    int res = 0;
    ll l = 1, r = 1e9;
    while(l <= r){
        int mid = (l+r)/2;
        if(check(mid)){
            res = mid;
            r = mid-1;
        } else {
            l = mid+1;
        }
    }

    cout << res << endl;
}
 main(){
    ios::sync_with_stdio(0);

    int T = 1;
    //cin >> T;
    for(int i = 1; i <= T; i++){
        test_case();
    }
}

Compilation message (stderr)

watching.cpp:65:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   65 |  main(){
      |       ^

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50