제출 #219179

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
219179		balbit	구경하기 (JOI13_watching)	C++14	100 / 100	850 ms	16248 KiB

watching

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

#define ll long long
#define SZ(x) (int)(x.size())
#define ALL(x) (x.begin(),x.end())
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S &&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define bug(...)
#define endl '\n'
#endif // BALBIT

const int maxn =  2004;

int n,p,q;
int a[maxn];
int pn[maxn], qn[maxn];
int dp[maxn][maxn];

bool ok(int w) {
    bug(w);
    int j = n-1;
    for (int i = n-1; i>=0; --i) {
        // pn records the last THING that it can reach
        while (a[j] - a[i] >= w) --j;
        pn[i] = j;
    }

    j = n-1;
    for (int i = n-1; i>=0; --i) {
        // qn records the last THING that it can reach
        while (a[j] - a[i] >= 2*w) --j;
        qn[i] = j;
    }
    pn[n] = qn[n] = n-1;
    for (int i = 0; i<maxn; ++i) fill(dp[i], dp[i]+ maxn, -0x3f3f3f3f);
    dp[0][0] = -1;
    for (int i = 0; i<=p; ++i) {
        for (int j = 0; j<=q; ++j) {
            if (i || j) {
                dp[i][j] = max(i?pn[dp[i-1][j]+1]:-1, j?qn[dp[i][j-1]+1]:-1);
            }
        }
    }
    bug(w,dp[p][q]);
    return dp[p][q] >=n-1;
}

signed main(){
    IOS();
    cin>>n>>p>>q;
    for (int i = 0; i<n; ++i) cin>>a[i];
    sort(a, a+n);
    p = min(p,n);
    q = min(q,n);
    int l = 1, r = 1e9+1;
    while (l!=r) {
        int mid = (l+r)/2;
        if (ok(mid)) {
            r = mid;
        }else{
            l = mid+1;
        }
    }
    cout<<l<<endl;
}

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