제출 #59379

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

watching

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

#define mp make_pair
#define pb push_back
#define fst first
#define snd second
#define int long long
#define MMAX 16384
#define fast_io() ios::sync_with_stdio(false)
#define FOR(i, l, r) for(int i = (l); i < (r); i++)

typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef set<int> si;
typedef double ld;
typedef pair<ld, ld> dd;

const ll INF = 1000000000000000000LL;
const int NMAX = 2e3+4;
const int mod = 1e9+7;
const ld eps = 1e-10;
const ld PI = acos(-1);

int w, N, P, Q;
vi A;

int dp2[NMAX][2];
int ub(int i, bool d){
    int &res = dp2[i][d];
    if(res != -1) return res;
    if(d) return res = upper_bound(A.begin(), A.end(), A[i]+2*w-1) - A.begin();
    else return res = upper_bound(A.begin(), A.end(), A[i]+  w-1) - A.begin();
}

int dp[NMAX][NMAX];
int leastQ(int i, int p){
    //cout << i << " " << p << endl;
    if(p < 0) return INF;
    int &res = dp[i][p];
    if(res != -1) return res;
    if(i == N) return res = 0;
    res = INF;
    res = min(res,     leastQ(ub(i, 0), p-1));
    res = min(res, 1 + leastQ(ub(i, 1), p  ));
    return res;
}

signed main(){
    fast_io();
    cin >> N >> P >> Q;
    A.resize(N);
    FOR(i, 0, N) cin >> A[i];
    sort(A.begin(), A.end());
    if(P+Q >= N) {
        cout << 1 << endl;
        return 0;
    }


    int lb = 0, rb = 1e9;
    while(lb+1 != rb){
        FOR(i, 0, NMAX) FOR(j, 0, NMAX) dp[i][j] = -1;
        FOR(i, 0, NMAX) FOR(j, 0, 2) dp2[i][j] = -1;
        w = (lb+rb)/2;
        if(leastQ(0, P) <= Q) rb = w;
        else lb = w;
    }
    cout << rb << endl;
}

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