oj.uz

답안 #1075227

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1075227 2024-08-25T20:56:43 Z ivaziva 구경하기 (JOI13_watching) C++14
0 / 100
 44 ms 16084 KB 
#include <bits/stdc++.h>

using namespace std;

#define MAXN 2001

int n,p,q;
int a[MAXN];
int dp[MAXN][MAXN];

bool check(int w)
{
    for (int i=0;i<MAXN;i++)
    {
        for (int j=0;j<MAXN;j++) dp[i][j]=INT_MAX;
    }
    dp[0][0]=0;
    for (int i=1;i<=n;i++)
    {
        int l1=0,r1=i-1;
        int pos1=i-1;
        while (l1<=r1)
        {
            int mid=(l1+r1)/2;
            if (a[i]-a[mid]>=w) {pos1=mid;l1=mid+1;}
            else r1=mid-1;
        }
        int l2=0,r2=i-1;
        int pos2=i-1;
        while (l2<=r2)
        {
            int mid=(l2+r2)/2;
            if (a[i]-a[mid]>=2*w) {pos2=mid;l2=mid+1;}
            else r2=mid-1;
        }
        for (long long j=0;j<=min(n,q);j++)
        {
            if (dp[pos1][j]==INT_MAX) continue;
            dp[i][j]=min(dp[i][j],dp[pos1][j]+1);
        }
        for (long long j=0;j<min(n,q);j++)
        {
            if (dp[pos2][j]==INT_MAX) continue;
            dp[i][j+1]=min(dp[i][j+1],dp[pos2][j]);
        }
    }
    for (long long i=0;i<=min(n,q);i++)
    {
        if (dp[n][i]<=p) return true;
        else continue;
    }
    return false;
}

int main()
{
    cin>>n>>p>>q;
    for (int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    int l=1,r=a[n];
    int rez=-1;
    while (l<=r)
    {
        int mid=(l+r)/2;
        if (check(mid)) {rez=mid;r=mid-1;}
        else l=mid+1;
    }
    cout<<rez<<endl;
}

Subtask #1
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 16084 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 15964 KB Output isn't correct
2 Halted 0 ms 0 KB -