제출 #946577

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
946577		VMaksimoski008	구경하기 (JOI13_watching)	C++14	0 / 100	59 ms	2136 KiB

watching

#include <bits/stdc++.h>

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

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=0;
                        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=0;
                        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=0, 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;
}

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