oj.uz

Submission #924109

# Submission time Handle Problem Language Result Execution time Memory
924109 2024-02-08T13:17:50 Z mariaclara Watching (JOI13_watching) C++17
0 / 100
 186 ms 31064 KB 
#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;

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

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

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

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Runtime error 23 ms 31064 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 186 ms 12972 KB Output is correct
4 Runtime error 24 ms 31064 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -