oj.uz

답안 #916726

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
916726 2024-01-26T11:48:56 Z Dec0Dedd 구경하기 (JOI13_watching) C++14
100 / 100
 300 ms 32192 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e3+10;
const int INF = 1e9+10;

ll a[N], n, p, q;

ll dp[N][N];
bool check(ll w) {
    for (int i=0; i<=n; ++i) {
        for (int j=0; j<=n; ++j) dp[i][j]=INF;
    }

    dp[0][0]=0;

    ll ppt=1, qpt=1;
    for (int i=1; i<=n; ++i) {
        while (a[i]-a[ppt]+1 > w) ++ppt;
        while (a[i]-a[qpt]+1 > 2*w) ++qpt;
        for (int j=1; j<=p; ++j) dp[i][j]=dp[ppt-1][j-1];
        for (int j=0; j<=p; ++j) dp[i][j]=min(dp[i][j], dp[qpt-1][j]+1);
    }

    for (int i=0; i<=p; ++i) {
        if (dp[n][i] <= q) return true;
    } return false;
} 

void solve() {
    cin>>n>>p>>q;
    for (int i=1; i<=n; ++i) cin>>a[i];
    sort(a+1, a+n+1);

    if (p+q >= n) {
        cout<<1<<"\n";
        return;
    }
    
    ll l=1, r=INF, res=INF;
    while (l <= r) {
        ll m=(l+r)/2;
        if (check(m)) res=m, r=m-1;
        else l=m+1;
    } cout<<res<<"\n";
}

int main() {
    int t=1; //cin>>t;
    while (t--) solve();
}

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 32192 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 107 ms 31832 KB Output is correct
8 Correct 157 ms 31992 KB Output is correct
9 Correct 190 ms 31836 KB Output is correct
10 Correct 300 ms 32084 KB Output is correct
11 Correct 127 ms 31932 KB Output is correct
12 Correct 216 ms 31928 KB Output is correct
13 Correct 115 ms 31836 KB Output is correct
14 Correct 112 ms 31836 KB Output is correct
15 Correct 113 ms 31936 KB Output is correct