제출 #924111

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
924111		mariaclara	Watching (JOI13_watching)	C++17	100 / 100	326 ms	16184 KiB

watching

#include<bits/stdc++.h>
#pragma GCC optimize ("O3")

using namespace std;

typedef long long ll;
typedef tuple<int,int,int> trio;
typedef pair<int,int> pii;
const int MAXN = 2e5+5;
const int MOD = 1e9+7;
#define all(x) x.begin(), x.end()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int n, p, q, v[2005], jump1[2005], jump2[2005], dp[2005][2005];

bool ok(int w) {
    for(int i = 1, j = 1, k = 1; i <= n; i++) {
        while(j <= n and v[j] - v[i] < w) j++;
        jump1[i] = j;

        while(k <= n and v[k] - v[i] < 2*w) k++;
        jump2[i] = k;
    }
    jump1[n+1] = jump2[n+1] = n+1;

    dp[0][0] = 1;
    for(int i = 1; i <= p; i++) dp[i][0] = jump1[dp[i-1][0]];
    for(int i = 1; i <= q; i++) dp[0][i] = jump2[dp[0][i-1]];

    for(int i = 1; i <= p; i++)
        for(int j = 1; j <= q; j++)
            dp[i][j] = max(jump1[dp[i-1][j]], jump2[dp[i][j-1]]);

    return dp[p][q] == n+1;
}

int busca() {
    int l = 1, r = 1e9;
    while(l <= r) {
        int meio = (l+r)/2;
        if(ok(meio)) r = meio-1;
        else l = meio+1;
    }
    return r+1;
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> p >> q;
    p = min(p, n);
    q = min(q, n);

    for(int i = 1; i <= n; i++)
        cin >> v[i];

    sort(v+1, v+1+n);

    cout << busca() << "\n";
}

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