제출 #1291075

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291075		haha	구경하기 (JOI13_watching)	C++20	100 / 100	57 ms	8740 KiB

watching

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=2e3+5;

int n,p,q;
int a[maxn];
int R[maxn],R2[maxn];
int dp[maxn][maxn];

// p small
// q large

bool check(int w)
{
    for(int i=1;i<=n;i++){
        R[i]=upper_bound(a+1,a+n+1,a[i]+w-1)-a-1;
        R2[i]=upper_bound(a+1,a+n+1,a[i]+2*w-1)-a-1;
    }
    for(int i=0;i<=p;i++){
        for(int j=0;j<=q;j++) dp[i][j]=0;
    }
    dp[0][0]=0;
    for(int x=0;x<=p;x++){
        for(int y=0;y<=q;y++){
            if(x>0){
                int id=dp[x-1][y];
                dp[x][y]=max(dp[x][y],R[id+1]);
            }
            if(y>0){
                int id=dp[x][y-1];
                dp[x][y]=max(dp[x][y],R2[id+1]);
            }
            if(dp[x][y]>=n) return true;
        }
    }
    return dp[p][q]==n;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>p>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    if(p+q>=n){
        cout<<1;
        return 0;
    }
    int l=1,r=a[n],ans;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    cout<<ans;
}

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