Submission #361322

#	Time	Username	Problem	Language	Result	Execution time	Memory
361322		mihai145	Watching (JOI13_watching)	C++14	100 / 100	510 ms	8684 KiB

watching

//
// Created by mihai145 on 29.01.2021.
//

#include <iostream>
#include <algorithm>

using namespace std;

const int NMAX = 2000;
const int L = 1e9;

int N, P, Q;
int a[NMAX + 5];

int dp[NMAX + 5][NMAX + 5];

bool ok(int w) {
    for (int i = 0; i <= P; i++) {
        for (int j = 0; j <= Q; j++) {
            dp[i][j] = 0;
        }
    }

    for(int i = 0; i <= P; i++) {
        for(int j = 0; j <= Q; j++) {
            ///we place one more small camera
            if(dp[i][j] >= N) {
                dp[i + 1][j] = dp[i][j];
            } else {
                int startIndex = dp[i][j] + 1;
                int st = startIndex, dr = N, sol = startIndex;
                while(st <= dr) {
                    int mid = (st + dr) >> 1;
                    if(a[mid] - a[startIndex] < w) {
                        sol = mid;
                        st = mid + 1;
                    } else {
                        dr = mid - 1;
                    }
                }

                dp[i + 1][j] = max(dp[i + 1][j], sol);
            }

            ///we place one more big camera
            if(dp[i][j] >= N) {
                dp[i][j + 1] = dp[i][j];
            } else {
                int startIndex = dp[i][j] + 1;
                int st = startIndex, dr = N, sol = startIndex;
                while(st <= dr) {
                    int mid = (st + dr) >> 1;
                    if(a[mid] - a[startIndex] < 2 * w) {
                        sol = mid;
                        st = mid + 1;
                    } else {
                        dr = mid - 1;
                    }
                }

                dp[i][j + 1] = max(dp[i][j + 1], sol);
            }
        }
    }

    return (dp[P][Q] >= N);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> P >> Q;

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

    ///P + Q < N

    for (int i = 1; i <= N; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + N + 1);

    int st = 1, dr = L, sol = L;
    while (st <= dr) {
        int mid = (st + dr) >> 1;
        if (ok(mid)) {
            sol = mid;
            dr = mid - 1;
        } else {
            st = mid + 1;
        }
    }

    cout << sol << '\n';

    return 0;
}

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