Submission #358630

#	Time	Username	Problem	Language	Result	Execution time	Memory
358630		blue	구경하기 (JOI13_watching)	C++17	100 / 100	223 ms	8812 KiB

watching

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, P, Q;
vector<int> A;
int moveW[2001], move2W[2001];
int dp[2001][2001]; //maximum index that can be reached with p small cameras and q large cameras

int b_search(int a, int b)
{
    if(a == b) return a;
    int w = (a+b)/2;

    for(int p = 0; p <= P; p++)
    {
        for(int q = 0; q <= Q; q++)
        {
            dp[p][q] = 0;
        }
    }


    int i, j = 0;
    for(i = 0; i < N; i++)
    {
        while(j < N && A[j+1] <= A[i+1] + w - 1) j++;
        moveW[i] = j;
    }
    moveW[N] = N;

    j = 0;
    for(i = 0; i <= N; i++)
    {
        while(j < N && A[j+1] <= A[i+1] + 2*w - 1) j++;
        move2W[i] = j;
    }
    move2W[N] = N;

    for(int p = 0; p <= P; p++)
    {
        for(int q = 0; q <= Q; q++)
        {
            if(p < P)
                dp[p+1][q] = max(dp[p+1][q], moveW[dp[p][q]]);
            if(q < Q)
                dp[p][q+1] = max(dp[p][q+1], move2W[dp[p][q]]);
        }
    }
    if(dp[P][Q] >= N)
        return b_search(a, w);
    else
        return b_search(w+1, b);
}

int main()
{
    cin >> N >> P >> Q;

    A = vector<int>(N+2);
    A[0] = 0;
    for(int i = 1; i <= N; i++) cin >> A[i];
    A[N+1] = 1e9;
    sort(A.begin(), A.end());

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

    cout << b_search(1, 5e8) << '\n';
}

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