oj.uz

Submission #916726

# Submission time Handle Problem Language Result Execution time Memory
916726 2024-01-26T11:48:56 Z Dec0Dedd Watching (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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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