oj.uz

Submission #944120

# Submission time Handle Problem Language Result Execution time Memory
944120 2024-03-12T08:40:49 Z goduadzesaba Watching (JOI13_watching) C++17
100 / 100
 211 ms 16208 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=2e3+5;
int n,p,q,l,r,md,ans,a[N],dp[N][N];
bool check(int w){
    for (int i=1; i<=n; i++){
        int l1=0, l2=0;
        for (int j=0; j<=n; j++) dp[i][j]=1e9;
        for (int j=i; j>=0; j--){
            while(a[l1+1]<=a[i]-w) l1++;
            while(a[l2+1]<=a[i]-2*w) l2++;
            if(j > 0) dp[i][j]=dp[l1][j-1];
            dp[i][j]=min(dp[i][j],dp[l2][j]+1);
        }
    }
    for (int i=0; i<=p; i++) {
        if(dp[n][i]<=q) return 1;
    }
    return 0;
}
int main() {
    cin>>n>>p>>q;
    p=min(p, n);
    q=min(q, n);
    for (int i=1; i<=n; i++)
        cin>>a[i];
    sort(a+1,a+n+1);
    l=1; r=1e9;
    while (l<=r){
        md=(l+r)/2;
        if (check(md)){
            ans=md; r=md-1;
        }
        else l=md+1;
    }
    cout<<ans;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 2 ms 2592 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 2 ms 2396 KB Output is correct
12 Correct 1 ms 2396 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 2488 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 16140 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 195 ms 16140 KB Output is correct
4 Correct 196 ms 16140 KB Output is correct
5 Correct 198 ms 15960 KB Output is correct
6 Correct 193 ms 15960 KB Output is correct
7 Correct 199 ms 16064 KB Output is correct
8 Correct 209 ms 16140 KB Output is correct
9 Correct 201 ms 15964 KB Output is correct
10 Correct 209 ms 16140 KB Output is correct
11 Correct 209 ms 15964 KB Output is correct
12 Correct 203 ms 16208 KB Output is correct
13 Correct 201 ms 16140 KB Output is correct
14 Correct 211 ms 16208 KB Output is correct
15 Correct 210 ms 16140 KB Output is correct