제출 #1155468

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155468		AlgorithmWarrior	Watching (JOI13_watching)	C++20	100 / 100	20 ms	8588 KiB

watching

#include <bits/stdc++.h>

using namespace std;

int const MAX=2005;
int n,small,big;
int v[MAX];

void read(){
    cin>>n>>small>>big;
    small=min(small,n);
    big=min(big,n);
    int i;
    for(i=1;i<=n;++i)
        cin>>v[i];
    sort(v+1,v+n+1);
}

int urmS[MAX],urmB[MAX];

void two_pointers(int w){
    int st,dr=1;
    for(st=1;st<=n;++st){
        while(dr<n && v[dr+1]-v[st]+1<=w)
            ++dr;
        urmS[st]=dr;
    }
    dr=1;
    for(st=1;st<=n;++st){
        while(dr<n && v[dr+1]-v[st]+1<=2*w)
            ++dr;
        urmB[st]=dr;
    }
}

int dp[MAX][MAX];

void maxself(int& x,int val){
    if(x<val)
        x=val;
}

bool get_dp(){
    int i,j;
    bool ok=0;
    for(i=0;i<=small && !ok;++i)
        for(j=0;j<=big && !ok;++j){
            dp[i][j]=0;
            if(i)
                maxself(dp[i][j],urmS[dp[i-1][j]+1]);
            if(j)
                maxself(dp[i][j],urmB[dp[i][j-1]+1]);
            if(dp[i][j]==n)
                ok=1;
        }
    return ok;
}

bool check(int w){
    two_pointers(w);
    return get_dp();
}

int bin_search(){
    /// (]
    int st=0,dr=1e9;
    while(dr-st>1){
        int mij=(st+dr)/2;
        if(check(mij))
            dr=mij;
        else
            st=mij;
    }
    return dr;
}

int main()
{
    read();
    cout<<bin_search();
    return 0;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50