답안 #499176

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
499176 2021-12-27T11:51:51 Z khoabright 구경하기 (JOI13_watching) C++17
0 / 100
75 ms 64300 KB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#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 = 1e15;
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, 1, 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';
        //if (dp[i][p] <= Q) return 1;
    }

    return dp[n][P] <= Q;
}

void solve() {
    cin >> n >> P >> Q;
    P = min(P, n);

    a.resize(n + 1);
    rep(i, 1, n) cin >> a[i];
    sort(all1(a));

   // cout << check(3) << '\n';
    int l = 1, r = n, ans = 0;
    while (l <= r) {
        int m = (l + r) >> 1;
        if (check(m)) {
            ans = m, r = m - 1;
        }
        else l = m + 1;
    }
  	assert(ans > 0);
    cout << ans;
}

main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    solve();
}

Compilation message

watching.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main() {
      | ^~~~
# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 1484 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 75 ms 64300 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -