제출 #1251781

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251781		Kel_Mahmut	Watching (JOI13_watching)	C++20	100 / 100	975 ms	4240 KiB

watching

#include <bits/stdc++.h>
#define pb push_back
#define endl ("\n")
#define all(aa) aa.begin(), aa.end()
typedef long long ll;
using namespace std;

int main(){
    int n, p, q;
    cin >> n >> p >> q;
    // p kucuk, q buyuk
    vector<ll> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    if(p + q >= n){
        cout << 1 << endl;
        exit(0);
    }
    a.pb(0);
    sort(all(a));
    function<int(int, ll)> get = [&](int pos, ll w){
        if(pos + 1 > n) return n;
        ll val = a[pos + 1] + w - 1;
        int ind = prev(upper_bound(all(a), val)) - a.begin();
        return ind;
    };

    ll tl = 0, tr = 1e9 + 5;
    vector<vector<int>> dp(p + 1, vector<int>(q + 1));
    function<int(ll)> ok = [&](ll w){
        for(int i = 0; i <= p; i++) for(int j = 0; j <= q; j++) dp[i][j] = 0;
        for(int i = 0; i <= p; i++){
            for(int j = 0; j <= q; j++){
                if(i - 1 >= 0){
                    dp[i][j] = max(dp[i][j], get(dp[i - 1][j], w));
                }
                if(j - 1 >= 0){
                    dp[i][j] = max(dp[i][j], get(dp[i][j - 1], w * 2));
                }
            }
        }
        return dp[p][q] >= n;
    };
    while(tr - tl > 1){
        ll tm = (tl + tr + 1) / 2;
        if(ok(tm))
            tr = tm;
        else
            tl = tm;
    }
    cout << tr << endl;
}

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