oj.uz

Submission #1107415

# Submission time Handle Problem Language Result Execution time Memory
1107415 2024-11-01T08:03:29 Z nasir_bashirov Watching (JOI13_watching) C++11
50 / 100
 136 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;
            }
        }
        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;
    }
    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 0 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 2384 KB Output is correct
13 Correct 1 ms 2384 KB Output is correct
14 Correct 1 ms 2556 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 7 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 504 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 10 ms 31428 KB Output is correct
8 Correct 18 ms 31312 KB Output is correct
9 Correct 72 ms 31640 KB Output is correct
10 Correct 136 ms 31824 KB Output is correct
11 Correct 13 ms 31276 KB Output is correct
12 Correct 73 ms 31568 KB Output is correct
13 Correct 7 ms 31312 KB Output is correct
14 Correct 7 ms 31312 KB Output is correct
15 Incorrect 7 ms 31312 KB Output isn't correct
16 Halted 0 ms 0 KB -