Submission #358629

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
358629	2021-01-26T02:40:53 Z	blue	Watching (JOI13_watching)	C++17	Compilation error	0 ms	0 KB

watching

#include <iostream>
#include <vector>
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';
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:64:5: error: 'sort' was not declared in this scope; did you mean 'qsort'?
   64 |     sort(A.begin(), A.end());
      |     ^~~~
      |     qsort