제출 #719084

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
719084		thimote75	구경하기 (JOI13_watching)	C++14	100 / 100	257 ms	16012 KiB

watching

#include <bits/stdc++.h>

using namespace std;

#define MAX_N 2000
#define inf 1e9

int nbEvents, nbSmall, nbLarge;
vector<int> eventTime;

vector<int> target_w;
vector<int> target_2w;

int dp[MAX_N][MAX_N];
int get_dp (int node, int picture) {
    if (picture == -1) return inf;
    if (node == -1) return 0;
    return dp[node][picture];
}

bool test_w (int w) {
    int l = -1;
    for (int r = 0; r < nbEvents; r ++) {
        while (eventTime[l + 1] + w <= eventTime[r])
            l ++;
        
        target_w[r] = l;
    }

    l = -1;
    for (int r = 0; r < nbEvents; r ++) {
        while (eventTime[l + 1] + 2 * w <= eventTime[r])
            l ++;
        
        target_2w[r] = l;
    }

    for (int i = 0; i < nbEvents; i ++) {
        for (int j = 0; j <= nbLarge; j ++) {
            dp[i][j] = min(
                get_dp(target_w[i], j) + 1,
                get_dp(target_2w[i], j - 1)
            );
        }
    }

    int min_p = inf;
    for (int j = 0; j <= nbLarge; j ++)
        min_p = min(min_p, dp[nbEvents - 1][j]);
    
    return min_p <= nbSmall;
}

int compute_w () {
    if (nbSmall + nbLarge >= nbEvents) return 1;

    int a = 0;
    int b = inf;

    while (b - a > 1) {
        int wc = (a + b) >> 1;

        if (test_w(wc)) b = wc;
        else a = wc;
    }
    
    return b;
}

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

    cin >> nbEvents >> nbSmall >> nbLarge;

    eventTime.resize(nbEvents);
    target_w .resize(nbEvents);
    target_2w.resize(nbEvents);

    for (int iE = 0; iE < nbEvents; iE ++)
        cin >> eventTime[iE];
    
    sort(eventTime.begin(), eventTime.end());

    cout << compute_w();
}

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