oj.uz

Submission #361319

# Submission time Handle Problem Language Result Execution time Memory
361319 2021-01-29T09:44:57 Z mihai145 Watching (JOI13_watching) C++14
0 / 100
 1 ms 364 KB 
//
// Created by mihai145 on 29.01.2021.
//

#include <iostream>

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] = 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] = 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];
    }

    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
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -