oj.uz

Submission #884052

# Submission time Handle Problem Language Result Execution time Memory
884052 2023-12-06T15:04:28 Z AlphaMale06 Watching (JOI13_watching) C++14
100 / 100
 80 ms 31704 KB 
#include <bits/stdc++.h>

#define int long long
#define F first
#define S second

using namespace std;

int dp[2001][2001];
int lft[2001][13];
int sum[2001][13];
int n, p, q, lg;

int lift(int ind, int pos){
    for(int j=lg-1; j>=0; j--){
        if(sum[ind][j]<=pos){
            pos-=sum[ind][j];
            ind=lft[ind][j];
        }
    }
    return ind;
}

bool ok(int s){
    dp[0][0]=-1;
    for(int i=1; i<=p; i++){
        dp[i][0]=lift(dp[i-1][0]+1, s-1);
    }
    for(int i=1; i<=q; i++){
        dp[0][i]=lift(dp[0][i-1]+1, 2*s-1);
    }
    if(dp[0][q]>= n-1 || dp[p][0]>=n-1)return 1;
    for(int i=1; i<=p; i++){
        for(int j=1; j<=q; j++){
            dp[i][j]=max(lift(dp[i-1][j]+1, s-1), lift(dp[i][j-1]+1, 2*s-1));
            if(p+q-i-j+dp[i][j]>=n-1){
                return 1;
            }
        }
    }
    if(dp[p][q]>=n-1)return 1;
    else return 0;
}

int bs(int l, int r){
     while(l<=r){
        int s=(l+r)/2;
        if(ok(s))r=s-1;
        else l=s+1;
    }
    return l;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> p >> q;
    lg=13;
    if(p+q>=n){
        cout << 1 << '\n';
        return 0;
    }
    int a[n];
    for(int i=0; i< n; i++)cin >> a[i];
    sort(a, a+n);
    for(int i=0; i< n-1; i++){
        lft[i][0]=i+1;
        sum[i][0]=a[i+1]-a[i];
    }
    lft[n-1][0]=n; lft[n][0]=n;
    for(int j=1; j<lg; j++){
        for(int i=0; i<= n; i++){
            lft[i][j]=lft[lft[i][j-1]][j-1];
            sum[i][j]=sum[lft[i][j-1]][j-1]+sum[i][j-1];
        }
    }
    cout << bs(1, 1000000000);
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 2396 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 0 ms 2396 KB Output is correct
8 Correct 0 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 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 0 ms 2420 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 0 ms 2392 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 0 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 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 2544 KB Output is correct
8 Correct 55 ms 4700 KB Output is correct
9 Correct 51 ms 12956 KB Output is correct
10 Correct 20 ms 31704 KB Output is correct
11 Correct 6 ms 2652 KB Output is correct
12 Correct 80 ms 17060 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 1 ms 2548 KB Output is correct