oj.uz

Submission #1107432

# Submission time Handle Problem Language Result Execution time Memory
1107432 2024-11-01T08:33:23 Z nasir_bashirov Watching (JOI13_watching) C++11
50 / 100
 156 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 j = 1; j <= n; j++) dp[j][0] = 1e18;
    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;
            }
        }
        for(int j = 1; j <= p; j++){
            // 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++;
            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;
    }
    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 504 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 2384 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 2552 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 9 ms 31568 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 576 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 9 ms 31312 KB Output is correct
8 Correct 18 ms 31456 KB Output is correct
9 Correct 64 ms 31568 KB Output is correct
10 Correct 156 ms 31824 KB Output is correct
11 Correct 13 ms 31312 KB Output is correct
12 Correct 103 ms 31568 KB Output is correct
13 Correct 8 ms 31312 KB Output is correct
14 Correct 8 ms 31312 KB Output is correct
15 Incorrect 7 ms 31312 KB Output isn't correct
16 Halted 0 ms 0 KB -