Submission #884047

#	Time	Username	Problem	Language	Result	Execution time	Memory
884047		AlphaMale06	구경하기 (JOI13_watching)	C++14	0 / 100	1 ms	2652 KiB

watching

#include <bits/stdc++.h>

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

using namespace std;

int dp[2001][2001];
int lft[2000][12];
int sum[2000][12];
int n, p, q;

int lift(int ind, int pos){
    for(int j=11; 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;
    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; i++)cout << a[i] << " ";
    cout << '\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<12; 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: 0 / 50
• Subtask 2: 0 / 50