oj.uz

Submission #1107450

# Submission time Handle Problem Language Result Execution time Memory
1107450 2024-11-01T08:53:56 Z Nelt Watching (JOI13_watching) C++17
50 / 100
 194 ms 31992 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]);
        }
    }
  	ll ans = q + 1;
  	for (ll i = 0; i <= p; i++) ans = min(ans, dp[n][i]);
    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;
     	for (ll i = 0; i <= n; i++)
        for (ll j = 0; j <= n; j++) dp[i][j] = 0;
        for(int j = 1; j <= n; j++) dp[j][0] = 1e18;
        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 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 2 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 74 ms 31824 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 67 ms 31824 KB Output is correct
8 Correct 60 ms 31992 KB Output is correct
9 Correct 104 ms 31824 KB Output is correct
10 Correct 194 ms 31880 KB Output is correct
11 Correct 74 ms 31824 KB Output is correct
12 Correct 148 ms 31824 KB Output is correct
13 Correct 57 ms 31824 KB Output is correct
14 Correct 49 ms 31824 KB Output is correct
15 Incorrect 56 ms 31824 KB Output isn't correct
16 Halted 0 ms 0 KB -