제출 #1270133

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270133		k12_khoi	Watching (JOI13_watching)	C++17	100 / 100	136 ms	460 KiB

watching

#include <bits/stdc++.h>
using namespace std;

const int N=2005;

int n,P,Q,res;
int a[N],dp_before[N],dp_cur[N];

bool check(int mid)
{
    int Lp;
    int lQ;

    dp_before[0]=dp_cur[0]=0;
    Lp=1;
    for (int i=1;i<=n;i++)
    {
        while (a[i]-a[Lp]+1>mid) Lp++;
        dp_before[i]=dp_before[Lp-1]+1;
    }

    if (dp_before[n]<=P) return true;


    for (int j=1;j<=Q;j++)
    {
        Lp=1;
        lQ=1;
        for (int i=1;i<=n;i++)
        {
            while (a[i]-a[Lp]+1>mid) Lp++;
            while (a[i]-a[lQ]+1>2*mid) lQ++;

            dp_cur[i]=dp_before[lQ-1];
            dp_cur[i]=min(dp_cur[i],dp_cur[Lp-1]+1);
        }

        for (int i=1;i<=n;i++)
        dp_before[i]=dp_cur[i];

        if (dp_cur[n]<=P) return true;
    }

    return false;
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> P >> Q;

    if (P+Q>=n)
    {
        cout << 1;
        return 0;
    }

    for (int i=1;i<=n;i++)
    cin >> a[i];

    sort(a+1,a+n+1);


    res=0;
    int l=1;
    int r=1e9;
    int mid;
    while (l<=r)
    {
        mid=(l+r)/2;
        if (check(mid))
        {
            res=mid;
            r=mid-1;
        }
        else l=mid+1;
    }

    cout << res;
}

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