제출 #492462

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
492462		ponytail	Watching (JOI13_watching)	C++17	0 / 100	217 ms	12100 KiB

watching

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
void solve(int tc) {
    int N, P, Q;
    cin >> N >> P >> Q;
    P = min(P, N);
    Q = min(Q, (N+1) / 2);
    int A[N+1];
    for(int i=1; i<=N; i++) cin >> A[i];
    sort(A+1, A+N+1);
    int lb = 1, rb = 1e9;
    while(lb < rb) {
        int w = (lb+rb) >> 1;
        int dp[P+1][Q+1]; // max index we can reach by P small and Q big
        dp[0][0] = 0;
        int sing[N+1], doub[N+1];
        for(int i=1; i<=N; i++) {
            for(int j=i; j<=N; j++) {
                if(A[j] - A[i] + 1 <= w) sing[i] = j;
                if(A[j] - A[i] + 1 <= 2*w) doub[i] = j;
            }
        }
        int idx = 0;
        for(int i=1; i<=P; i++) {
            dp[i][0] = (idx == N ? N : sing[idx + 1]);
            idx = dp[i][0];
        }
        idx = 0;
        for(int i=1; i<=Q; i++) {
            dp[0][i] = (idx == N ? N : doub[idx + 1]);
            idx = dp[0][i];
        }
        for(int i=1; i<=P; i++) {
            for(int j=1; j<=Q; j++) {
                dp[i][j] = max(
                    (dp[i-1][j] == N ? N : sing[dp[i-1][j] + 1]),
                    (dp[i][j-1] == N ? N : doub[dp[i][j-1] + 1])
                );
            }
        }
        if(dp[P][Q] == N) rb = w;
        else lb = w+1;
    }
    cout << lb << "\n";
}
signed main() {
    int t = 1;
    //cin >> t;
    for(int i=1; i<=t; i++) {
        solve(i);
    }
}

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