oj.uz

답안 #499225

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
499225 2021-12-27T13:24:48 Z khoabright 구경하기 (JOI13_watching) C++17
0 / 100
 72 ms 16068 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define rep(i, a, b) for (int i = (int)a; i <= (int)b; ++i)
#define rep1(i, a, b) for (int i = (int)a; i >= (int)b; --i)
#define all(x) x.begin(), x.end()
#define all1(x) x.begin() + 1, x.end()
 
int n, P, Q;
vector<int> a;
const int N = 2005;
const int inf = 1e9;
int L[N][2];
int dp[N][N];
 
bool check(int w) {
    rep(i, 0, n + 2) rep(j, 0, n + 2) {
        dp[i][j] = inf;
    }
 
    rep(i, 1, n) {
        L[i][0] = lower_bound(all1(a), a[i] - w + 1) - a.begin();
        L[i][1] = lower_bound(all1(a), a[i] - 2 * w + 1) - a.begin();
    }
 
//    rep(i, 1, n) {
//        cout << L[i][0] << ' ' << L[i][1] << '\n';
//    }
 
    rep(i, 0, P) dp[0][i] = 0;
 
    rep(i, 1, n) rep(p, 0, P) {
        dp[i][p] = min(dp[L[i][0] - 1][p - 1], dp[L[i][1] - 1][p] + 1);
        //cout<<"i,p,dp="<<i<<' '<<p<<' '<<dp[i][p]<<'\n';
    }
 
    return dp[n][P] <= Q;
}
 
void solve() {
    cin >> n >> P >> Q;
    P = min(P, n);
    Q = min(Q, n);
    a.resize(n + 1);
    rep(i, 1, n) cin >> a[i];
    sort(all1(a));
 
   // cout << check(3) << '\n';
    int l = 1, r = inf, ans = 0;
    while (l <= r) {
        int m = (l + r) >> 1;
        if (check(m)) {
            ans = m, r = m - 1;
        }
        else l = m + 1;
    }
    cout << ans;
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); 
    solve();
}

Subtask #1
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 72 ms 16068 KB Output isn't correct
2 Halted 0 ms 0 KB -