oj.uz

Submission #1107419

# Submission time Handle Problem Language Result Execution time Memory
1107419 2024-11-01T08:08:41 Z nasir_bashirov Watching (JOI13_watching) C++11
50 / 100
 190 ms 31824 KB 
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define db long double
#define vll vector<pll>
#define endl '\n'
#define all(x) x.begin(), x.end()
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
#define int long long
 
const int sz = 2e3 + 5;
int n, p, q, dp[sz][sz], a[sz];
 
int check(int w){
    for(int i = 1; i <= n; i++){
        int i1 = 0, i2 = 0;
        // int l = 1, r = i - 1;
        // while(l <= r){
        //     int mid = (l + r) / 2;
        //     if(a[mid] + w <= a[i]){
        //         i1 = mid;
        //         l = mid + 1;
        //     }
        //     else{
        //         r = mid - 1;
        //     }
        // }
        // l = 1, r = i - 1;
        // while(l <= r){
        //     int mid = (l + r) / 2;
        //     if(a[mid] + 2 * w <= a[i]){
        //         i2 = mid;
        //         l = mid + 1;
        //     }
        //     else{
        //         r = mid - 1;
        //     }
        // }
        while(i1 + 1 <= n and a[i1 + 1] + w <= a[i]) i1++;
        while(i2 + 1 <= n and a[i2 + 1] + w * 2 <= a[i]) i2++;
        for(int j = 1; j <= p; j++){
            dp[i][j] = min(dp[i2][j] + 1, dp[i1][j - 1]);
        }
    }
    return dp[n][p];
}
 
void fmain(){
    fastio;
    cin >> n >> p >> q;
    if(p + q >= n){
        cout << 1;
        return;
    }
    for(int j = 1; j <= n; j++) dp[j][0] = 1e18;
    p = min(n, p), q = min(n, q);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    int l = 1, r = 1e18 / (p + q), res = -1;
    while(l <= r){
        int mid = (l + r) / 2;
        if(check(mid) <= q){
            res = mid;
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    cout << res;
}
 
signed main(){
    int tmr = 1;
    // cin >> tmr;
    while(tmr--){
        fmain();
    }
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 2556 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 1 ms 2384 KB Output is correct
11 Correct 1 ms 2384 KB Output is correct
12 Correct 1 ms 2384 KB Output is correct
13 Correct 1 ms 2384 KB Output is correct
14 Correct 1 ms 2384 KB Output is correct
15 Correct 1 ms 2384 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 31312 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 66 ms 31416 KB Output is correct
8 Correct 67 ms 31312 KB Output is correct
9 Correct 109 ms 31568 KB Output is correct
10 Correct 190 ms 31824 KB Output is correct
11 Correct 66 ms 31476 KB Output is correct
12 Correct 133 ms 31568 KB Output is correct
13 Correct 54 ms 31480 KB Output is correct
14 Correct 54 ms 31312 KB Output is correct
15 Incorrect 56 ms 31312 KB Output isn't correct
16 Halted 0 ms 0 KB -