Submission #976045

#	Time	Username	Problem	Language	Result	Execution time	Memory
976045		vjudge1	Watching (JOI13_watching)	C++17	100 / 100	411 ms	30344 KiB

watching

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

#define ll long long
#define v(a) vector<a>
template<typename T>
void print(vector<T> var) { // print vector
        for(auto i : var) {
                cout << i << ' ';
        } cout << endl;
}

ll n, p, q;
v(v(ll)) dp;
v(ll) arr, nextP, nextQ;

ll trav(ll idx, ll cur){
    if(idx >= n) return 0;
    if(cur < 0) return 1e9;
    if(dp[idx][cur] != -1) return dp[idx][cur];

    ll ret = 1e9;
    ret = trav(nextP[idx], cur)+1;
    if(cur > 0) ret = min(ret, trav(nextQ[idx], cur-1));
    return dp[idx][cur] = ret;
}

ll binsearch(ll l, ll r){
    if(l <= r){
        ll mid = (l+r)/2;
        nextP.clear();
        nextQ.clear();
        nextP.assign(n+1, n);
        nextQ.assign(n+1, n);

        // nextP
        // cout << mid << endl;
        for(int i = 0; i < n; i++){
            ll cur = arr[i]+mid;
            for(int j = i+1; j < n; j++){
                if(arr[j]+1 > cur){
                    nextP[i] = j;
                    break;
                }
            }
        }

        // nextQ
        for(int i = 0; i < n; i++){
            ll cur = arr[i]+2*mid;
            for(int j = i+1; j < n; j++){
                if(arr[j]+1 > cur){
                    nextQ[i] = j;
                    break;
                }
            }
        }
        // print(nextP);
        // print(nextQ);
        //reset DP
        for(int i = 0; i < n; i++){
            dp[i].clear();
            dp[i].assign(q+1, -1);
        }

        if(trav(0, q) <= p) return min(mid, binsearch(l, mid-1));
        return binsearch(mid+1, r);
    }

    return 1e9;
}

int main(){
cin >> n >> p >> q;
dp.resize(n+5);
arr.resize(n);
for(int i = 0; i < n; i++) cin >> arr[i];
sort(arr.begin(), arr.end());

if(p + q >= n) cout << 1;
else {
    // p = min(p, n);
    q = min(q, n);
    cout << binsearch(1, 1e9) << '\n';
}
}

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