oj.uz

Submission #907110

# Submission time Handle Problem Language Result Execution time Memory
907110 2024-01-15T07:06:07 Z typ_ik Watching (JOI13_watching) C++17
50 / 100
 47 ms 262144 KB 
#include <bits/stdc++.h>

#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define watch(x) cout << (#x) << " : " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

using namespace std;  

const int N = 2222;
bitset <N> bs[N][N]; 
int a[N];

void solve() { 
    int n, p, q;
    cin >> n >> p >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    sort(a + 1, a + n + 1);
    
    if (p + q >= n) {
        cout << 1 << '\n';
        return;
    } 

    auto check = [&](int w) -> bool {   
        for (int i = 0; i <= n; i++)
            for (int c = 0; c <= p; c++)    
                bs[i][c].reset();
        for (int i = 0; i <= p; i++)
            for (int j = 0; j <= q; j++)
                bs[0][i][j] = 1; 
        int j0 = 0, j1 = 0; 

        for (int i = 1; i <= n; i++) {
            // place w.
            while (j0 + 1 <= n && a[j0 + 1] - a[i] + 1 <= w)
                j0++;
            while (j1 + 1 <= n && a[j1 + 1] - a[i] + 1 <= 2*w)
                j1++;  

            for (int lp = 0; lp <= p; lp++)
                bs[j0][lp] |= bs[i-1][lp+1]; 
             
            for (int lp = 0; lp <= p; lp++)
                bs[j1][lp] |= (bs[i-1][lp] >> 1); 
        }  

        return bs[n][0][0];
    };   

    int l = 0, r = 1e9 + 128;
    while (l + 1 < r) {
        int m = (l + r) >> 1;
        if (check(m))
            r = m;
        else 
            l = m;
    }

    cout << r << '\n';
}

main() { 
    boost;  
    solve();
    return 0;
}

Compilation message

watching.cpp:66:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   66 | main() {
      | ^~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 61784 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 6488 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 11 ms 61788 KB Output is correct
8 Correct 12 ms 61788 KB Output is correct
9 Correct 16 ms 62032 KB Output is correct
10 Correct 16 ms 61932 KB Output is correct
11 Correct 32 ms 61984 KB Output is correct
12 Correct 33 ms 61964 KB Output is correct
13 Correct 11 ms 62000 KB Output is correct
14 Correct 13 ms 61788 KB Output is correct
15 Correct 13 ms 61784 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 47 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -