제출 #1145072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1145072		roumak	Watching (JOI13_watching)	C++20	100 / 100	895 ms	30308 KiB

watching

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <limits>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
using namespace std;

using ll = long long;
ll INF = 2 * 1E9;
void solve(){

    ll n, p, q;
    cin >> n >> p >> q;

    vector<ll> list_n(n, 0);

    for(ll i = 0; i < n; i++){
        cin >> list_n[i];
    }
    sort(list_n.begin(), list_n.end());

    if(p + q >= n){
        cout << 1 << endl;
        return;
    }
    ll l = 1;
    ll r = INF;

    while(l + 1 < r){
        ll mid = (l + r)/2;
        vector<vector<ll>> dp(n + 1, vector<ll>(p + 1, INF));
        dp[0][0] = 0;
        for(ll i = 0; i < n; i++){
            for (int j = 0; j <= p; j++) {
                if(dp[i][j] == INF){
                    continue;
                }
                if(j != p){
                    ll left = i;
                    ll right = n;
                    while(left + 1 < right){
                        ll middle = (left + right)/2;

                        if(list_n[middle] < list_n[i] + mid){
                            left = middle;
                        }else{
                            right = middle;
                        }

                    }
                    dp[left + 1][j + 1] = min(dp[i][j], dp[left + 1][j + 1]);
                }

                // Increase the bigger thingy
                ll left = i;
                ll right = n;
                while(left + 1 < right){
                    ll middle = (left + right)/2;

                    if(list_n[middle] < list_n[i] + 2*mid){
                        left = middle;
                    }else{
                        right = middle;
                    }

                }
                dp[left + 1][j] = min(dp[i][j] + 1, dp[left + 1][j]);

            }
        }

        bool pos = false;
        for(ll i = 0; i <= p; i++){
            if(dp[n][i] <= q){
                pos = true;
                break;
            }
        }
        //cout << mid << " " << pos << endl;

        if(pos){
            r = mid;
        }else{
            l = mid;
        }
    }

    cout << r;



}

bool single = true;

signed main(){

    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    ll t = 1;
    if(!single) cin >> t;

    while(t--){
        solve();
    }
}

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