oj.uz

Submission #1060318

# Submission time Handle Problem Language Result Execution time Memory
1060318 2024-08-15T12:57:00 Z phong Watching (JOI13_watching) C++17
100 / 100
 233 ms 16220 KB 
#include<bits/stdc++.h>

#define ll long long
const int nmax =  2e3+ 5, N = 1e6;
const ll oo = 1e18 + 1, base = 311;
const int lg = 19, M = 10;
const ll mod = 1e9 + 2277, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n, p, q;
int a[nmax];
int dp[nmax][nmax];
void ckmax(int &a, int b){
    a = max(a, b);
}
bool check(int mid){
    memset(dp, -1,sizeof dp);
    dp[0][0] = 0;
    for(int i = 0; i <= p; ++i){
        for(int j = 0; j <= q; ++j){
            if(dp[i][j] == n) return 1;
            if(dp[i][j] != -1 ){
                int x = dp[i][j] + 1;
                int it = upper_bound(a + x + 1, a + 1 + n, a[x] + mid - 1) - a - 1;
                ckmax(dp[i + 1][j], it);
                it = upper_bound(a + x + 1, a + 1 + n, a[x] + 2 * mid - 1) - a - 1;
                ckmax(dp[i][j + 1], it);
            }
        }
    }
    return 0;
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> p >> q;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + 1 + n);
    if(p + q >= n) cout << 1, exit(0);
    int l =1, r = 1e9, kq =-1;
    while(l <= r){
        int mid = r + l >> 1;
        if(check(mid)){
            kq = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    cout << kq;
}
/*
a[mid] - a[x] > w


*/

Compilation message

watching.cpp:38:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   38 | main(){
      | ^~~~
watching.cpp: In function 'int main()':
watching.cpp:49:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         int mid = r + l >> 1;
      |                   ~~^~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15960 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 11 ms 16192 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 12 ms 16200 KB Output is correct
8 Correct 12 ms 16012 KB Output is correct
9 Correct 11 ms 15976 KB Output is correct
10 Correct 11 ms 15964 KB Output is correct
11 Correct 11 ms 15964 KB Output is correct
12 Correct 12 ms 15964 KB Output is correct
13 Correct 10 ms 15964 KB Output is correct
14 Correct 10 ms 15960 KB Output is correct
15 Correct 11 ms 15960 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16220 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 11 ms 16220 KB Output is correct
8 Correct 43 ms 16196 KB Output is correct
9 Correct 48 ms 16216 KB Output is correct
10 Correct 63 ms 16192 KB Output is correct
11 Correct 29 ms 16216 KB Output is correct
12 Correct 233 ms 16220 KB Output is correct
13 Correct 13 ms 16216 KB Output is correct
14 Correct 12 ms 16220 KB Output is correct
15 Correct 13 ms 16216 KB Output is correct