oj.uz

Submission #867245

# Submission time Handle Problem Language Result Execution time Memory
867245 2023-10-28T02:33:06 Z Eliorita Watching (JOI13_watching) C++14
100 / 100
 287 ms 31836 KB 
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define x first
#define y second
#define getbit(u,i) ((u>>i)&1)
#define all(x) x.begin(),x.end()
#define N 200001
using namespace std;
typedef pair<int,int> ii;
typedef pair<double,double> dd;
int n,a,b,A[N],dp[2001][2001],ans,l=1,r=1e9+8;
bool check(int x)
{
    int mn=LLONG_MAX;
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=n;i++)
    {
        int l=1,r=1;
        while(l<i&&A[i]>=x+A[l]) l++;
        for(int j=0;j<=b;j++) dp[i][j]=dp[l-1][j]+1;
        while(r<i&&A[i]>=2*x+A[r]) r++;
        for(int j=0;j<=b;j++) dp[i][j+1]=min(dp[i][j+1],dp[r-1][j]);
    }
    for(int i=0;i<=b;i++) mn=min(mn,dp[n][i]);
    return mn<=a;
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>a>>b;
    if(n<=a+b) {cout<<1; return 0;}
    for(int i=1;i<=n;i++) cin>>A[i];
    sort(A+1,A+n+1);
    while(l<=r)
    {
        int m=(l+r)/2;
        if(check(m))
        {
            ans=m;
            r=m-1;
        }
        else l=m+1;
    }
    cout<<ans;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 31576 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 62 ms 31580 KB Output is correct
4 Correct 0 ms 600 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 65 ms 31580 KB Output is correct
8 Correct 64 ms 31580 KB Output is correct
9 Correct 65 ms 31780 KB Output is correct
10 Correct 63 ms 31580 KB Output is correct
11 Correct 65 ms 31776 KB Output is correct
12 Correct 64 ms 31580 KB Output is correct
13 Correct 64 ms 31580 KB Output is correct
14 Correct 62 ms 31576 KB Output is correct
15 Correct 61 ms 31580 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 31800 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 108 ms 31816 KB Output is correct
8 Correct 196 ms 31836 KB Output is correct
9 Correct 129 ms 31580 KB Output is correct
10 Correct 123 ms 31576 KB Output is correct
11 Correct 287 ms 31812 KB Output is correct
12 Correct 206 ms 31832 KB Output is correct
13 Correct 106 ms 31832 KB Output is correct
14 Correct 117 ms 31836 KB Output is correct
15 Correct 111 ms 31812 KB Output is correct