oj.uz

Submission #518839

# Submission time Handle Problem Language Result Execution time Memory
518839 2022-01-24T23:09:32 Z Marceantasy Watching (JOI13_watching) C++17
100 / 100
 641 ms 16040 KB 
#include <bits/stdc++.h>
using namespace std; 

#define ll long long
#define ar array

const int mxN = 2005, M = 1e9+7;
int n, p, q, a[mxN];
int nxt1[mxN], nxt2[mxN];

int dp[mxN][mxN];

bool trial(int pos){
    for(int i = 0; i<n; ++i){
        nxt1[i] = (int)(lower_bound(a, a+n, a[i]+pos)-a);
        nxt2[i] = (int)(lower_bound(a, a+n, a[i]+2*pos)-a);
    }
    nxt1[n] = nxt2[n] = n;
    for(int i = p; i>=0; --i){
        for(int j = q; j>=0; --j){
            if(i == p && j == p) continue;
            int ans = 0;
            if(i != p){
                ans = max(ans, nxt1[dp[i+1][j]]);
            }
            if(j != q){
                ans = max(ans, nxt2[dp[i][j+1]]);
            }
            dp[i][j] = ans;
        }
    }
    return dp[0][0] >= n;
}

int main(){
#ifdef _DEBUG
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
    std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);

    cin >> n >> p >> q;
    for(int i = 0; i<n; ++i){
        cin >> a[i];
    }
    p = min(p, n);
    q = min(q, n);
    sort(a, a+n); 
    int l = 0, r = 1e9;
    while(l<r){
        int mid = (l+r)/2;
        if(trial(mid)) r = mid;
        else l = mid+1;
    }
    cout << l << "\n";
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 680 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 324 KB Output is correct
11 Correct 1 ms 452 KB Output is correct
12 Correct 1 ms 444 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 375 ms 12124 KB Output is correct
4 Correct 32 ms 8908 KB Output is correct
5 Correct 30 ms 972 KB Output is correct
6 Correct 641 ms 16040 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 19 ms 1096 KB Output is correct
9 Correct 19 ms 3660 KB Output is correct
10 Correct 34 ms 8640 KB Output is correct
11 Correct 32 ms 1044 KB Output is correct
12 Correct 168 ms 8012 KB Output is correct
13 Correct 5 ms 332 KB Output is correct
14 Correct 6 ms 332 KB Output is correct
15 Correct 6 ms 332 KB Output is correct