oj.uz

Submission #977277

# Submission time Handle Problem Language Result Execution time Memory
977277 2024-05-07T15:45:22 Z LOLOLO Watching (JOI13_watching) C++17
100 / 100
 218 ms 17748 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
#define           f    first
#define           s    second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 2e3 + 100;
int a[N], n, p, q;
int f[N][N];

bool check(int w) {
    mem(f, 0x3f);
    f[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        int l1 = lower_bound(a + 1, a + 1 + n, a[i] - w + 1) - a;
        int l2 = lower_bound(a + 1, a + 1 + n, a[i] - 2 * w + 1) - a;
        for (int j = 0; j <= n; j++) {
            if (j) {
                f[i][j] = min(f[i][j], f[l2 - 1][j - 1]);
            } 

            f[i][j] = min(f[i][j], f[l1 - 1][j] + 1);
        }
    }

    for (int i = 1; i <= q; i++) {
        if (f[n][i] <= p)
            return 1;
    }

    return 0;
}

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> p >> q;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    sort(a + 1, a + n + 1);

    int l = 1, r = 1e9, m, ans;
    while (l <= r) {
        m = (l + r) / 2;
        if (check(m)) {
            ans = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }

    cout << ans << '\n';

    return 0;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:74:20: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |     cout << ans << '\n';
      |                    ^~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 17496 KB Output is correct
2 Correct 26 ms 17724 KB Output is correct
3 Correct 28 ms 17500 KB Output is correct
4 Correct 27 ms 17500 KB Output is correct
5 Correct 26 ms 17500 KB Output is correct
6 Correct 27 ms 17500 KB Output is correct
7 Correct 27 ms 17500 KB Output is correct
8 Correct 36 ms 17740 KB Output is correct
9 Correct 29 ms 17704 KB Output is correct
10 Correct 26 ms 17724 KB Output is correct
11 Correct 29 ms 17728 KB Output is correct
12 Correct 29 ms 17500 KB Output is correct
13 Correct 31 ms 17712 KB Output is correct
14 Correct 29 ms 17500 KB Output is correct
15 Correct 28 ms 17496 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 17704 KB Output is correct
2 Correct 26 ms 17500 KB Output is correct
3 Correct 167 ms 17500 KB Output is correct
4 Correct 171 ms 17724 KB Output is correct
5 Correct 174 ms 17748 KB Output is correct
6 Correct 170 ms 17496 KB Output is correct
7 Correct 198 ms 17496 KB Output is correct
8 Correct 193 ms 17748 KB Output is correct
9 Correct 191 ms 17724 KB Output is correct
10 Correct 177 ms 17728 KB Output is correct
11 Correct 187 ms 17724 KB Output is correct
12 Correct 218 ms 17496 KB Output is correct
13 Correct 180 ms 17728 KB Output is correct
14 Correct 176 ms 17500 KB Output is correct
15 Correct 200 ms 17496 KB Output is correct