제출 #946582

#제출 시각아이디문제언어결과실행 시간메모리
946582VMaksimoski008구경하기 (JOI13_watching)C++14
50 / 100
768 ms2140 KiB
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;

vector<vector<vector<bool> > > dp(105, vector<vector<bool>>(105, vector<bool>(105)));

int main() {
    int n, p, q;
    cin >> n >> p >> q;

    p = min(n, p);
    q = min(n, q);

    vector<int> v(n+1);
    for(int i=1; i<=n; i++) cin >> v[i];
    sort(1+all(v));

    auto f = [&](int mid) {
        for(int i=0; i<=n; i++)
            for(int j=0; j<=p; j++)
                for(int k=0; k<=q; k++) dp[i][j][k] = 0;

        dp[0][0][0] = 1;

        for(int i=1; i<=n; i++) {
            for(int j=0; j<=p; j++) {
                for(int k=0; k<=q; k++) {
                    if(j) {
                        int l=1, r=i, pos=i;
                        while(l <= r) {
                            int m = (l + r) / 2;
                            if(v[i] - v[m] < mid) pos = m, r = m - 1;
                            else l = m + 1;
                        }
                        if(dp[pos-1][j-1][k]) dp[i][j][k] = 1;
                    }

                    if(k) {
                        int l=1, r=i, pos=i;
                        while(l <= r) {
                            int m = (l + r) / 2;
                            if(v[i] - v[m] < 2ll * mid) pos = m, r = m - 1;
                            else l = m + 1;
                        }
                        if(dp[pos-1][j][k-1]) dp[i][j][k] = 1;
                    }
                }
            }
        }

        for(int i=0; i<=p; i++)
            for(int j=0; j<=q; j++)
                if(dp[n][i][j]) return 1;
        return 0;
    };

    int l=1, r=1e9, ans = 1e9;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(f(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }

    cout << ans << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...