Submission #518839

#	Time	Username	Problem	Language	Result	Execution time	Memory
518839		Marceantasy	Watching (JOI13_watching)	C++17	100 / 100	641 ms	16040 KiB

watching

#include <bits/stdc++.h>
using namespace std; 

#define ll long long
#define ar array

const int mxN = 2005, M = 1e9+7;
int n, p, q, a[mxN];
int nxt1[mxN], nxt2[mxN];

int dp[mxN][mxN];

bool trial(int pos){
    for(int i = 0; i<n; ++i){
        nxt1[i] = (int)(lower_bound(a, a+n, a[i]+pos)-a);
        nxt2[i] = (int)(lower_bound(a, a+n, a[i]+2*pos)-a);
    }
    nxt1[n] = nxt2[n] = n;
    for(int i = p; i>=0; --i){
        for(int j = q; j>=0; --j){
            if(i == p && j == p) continue;
            int ans = 0;
            if(i != p){
                ans = max(ans, nxt1[dp[i+1][j]]);
            }
            if(j != q){
                ans = max(ans, nxt2[dp[i][j+1]]);
            }
            dp[i][j] = ans;
        }
    }
    return dp[0][0] >= n;
}

int main(){
#ifdef _DEBUG
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
    std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);

    cin >> n >> p >> q;
    for(int i = 0; i<n; ++i){
        cin >> a[i];
    }
    p = min(p, n);
    q = min(q, n);
    sort(a, a+n); 
    int l = 0, r = 1e9;
    while(l<r){
        int mid = (l+r)/2;
        if(trial(mid)) r = mid;
        else l = mid+1;
    }
    cout << l << "\n";
}

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