제출 #1222245

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222245		toast12	Watching (JOI13_watching)	C++20	0 / 100	1 ms	324 KiB

watching

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

using ll = long long;

int main() {
    int n, p, q;
    cin >> n >> p >> q;
    vector<int> a(n+1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    a[0] = 0;
    if (p+q >= n) {
        cout << 1 << '\n';
        return 0;
    }
    ll lo = 1, hi = 1e9;
    while (lo < hi) {
        ll mid = (lo+hi)/2;
        // check if w = mid is a valid answer
        vector<int> idx1(n+1), idx2(n+1);
        int j = 0;
        for (int i = 0; i <= n; i++) {
            // if a small camera is placed at a[i+1], what is the maximum index it can reach?
            while (j+1 <= n && a[j+1]-a[i+1]+1 <= mid) j++;
            idx1[i] = j;
        }
        idx1[n] = n;
        j = 0;
        for (int i = 0; i <= n; i++) {
            // same but for a large camera
            while (j+1 <= n && a[j+1]-a[i+1]+1 <= 2*mid) j++;
            idx2[i] = j;
        }
        idx2[n] = n;
        vector<vector<int>> dp(p+1, vector<int>(q+1));
        // dp[i][j] stores the maximum possible index reachable using i small cameras and j large cameras
        for (int i = 0; i <= p; i++) {
            for (int j = 0; j <= q; j++) {
                if (i+1 <= p) dp[i+1][j] = max(dp[i+1][j], idx1[dp[i][j]]);
                if (j+1 <= q) dp[i][j+1] = max(dp[i][j+1], idx2[dp[i][j]]);
            }
        }
        bool poss = false;
        for (int i = 0; i <= p; i++) {
            for (int j = 0; j <= q; j++) {
                if (dp[i][j] >= n) {
                    poss = true;
                    break;
                }
            }
            if (poss) break;
        }
        if (poss) hi = mid;
        else lo = mid+1;
    }
    cout << hi << '\n';
    return 0;
}

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