Submission #1257514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257514		jahongir	Watching (JOI13_watching)	C++20	100 / 100	51 ms	8304 KiB

watching

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T> using ordered_set = tree<T,null_type,less_equal<T>,rb_tree_tag,
					 tree_order_statistics_node_update>;
 
#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define pb push_back
#define all(a) a.begin(),a.end()


const int mxn = 2005;
int arr[mxn], n,p,q;
short dp[mxn][mxn];

short suc[mxn][2];

bool check(int w){
    for(int l = n, r = n; l; l--){
        while(arr[r]-arr[l] >= w) r--;
        suc[l][0] = r+1;
    }
    for(int l = n, r = n; l; l--){
        while(arr[r]-arr[l] >= 2*w) r--;
        suc[l][1] = r+1;
    }

    for(int i = 0; i <= p; i++)
        for(int j = 0; j <= q && i+j <= n; j++)
            dp[i][j] = 0;

    dp[0][0] = 1;

    for(int i = 0; i <= p; i++)
        for(int j = 0; j <= q && i+j <= n; j++){
            if(dp[i][j]==n+1) return true;

            dp[i+1][j] = max(dp[i+1][j],suc[dp[i][j]][0]);
            dp[i][j+1] = max(dp[i][j+1],suc[dp[i][j]][1]);
        }
    
    return false;
}


void solve(){
    cin >> n >> p >> q;
    for(int i = 1; i <= n; i++) cin >> arr[i];
    sort(arr+1,arr+n+1);

    int l = 0, r = 1e9;

    while(l+1 < r){
        int mid = (l+r)>>1;
        if(check(mid)) r = mid;
        else l = mid;
    }

    cout << r;
}


signed main(){
    // freopen("cave.in","r",stdin);
    // freopen("cave.out","w",stdout);
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while(t--) solve();
}

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