oj.uz

Submission #1076017

# Submission time Handle Problem Language Result Execution time Memory
1076017 2024-08-26T10:32:15 Z andrewp Watching (JOI13_watching) C++14
100 / 100
 186 ms 16228 KB 
//Dedicated to my love, ivaziva
#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
using ll = int64_t;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define dbg(x) cerr << #x << ": " << x << '\n'; 

constexpr int N = 2e3 + 5, W = (int)1e9 + 10;
int n, p, q, a[N], dp[N][N];

bool check(int w) {     
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = W;
        }
    }
    dp[0][0] = 0;
    int f = 0, s = 0;
    for (int i = 1; i <= n; i++) {
        while (a[i] >= a[f + 1] + w) {
            f++;
        }
        while (a[i] >= a[s + 1] + 2 * w) {
            s++;
        }
        for (int j = 0; j <= n; j++) {
            dp[i][j] = dp[f][j] + 1;
            if (j) {
                dp[i][j] = min(dp[i][j], dp[s][j - 1]);
            }
        }
    }
    for (int i = 0; i <= min(n, q); i++) {
        if (dp[n][i] <= p) {
            return true;
        }
    }
    return false;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cout.tie(nullptr); cerr.tie(nullptr);

    cin >> n >> p >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    int l = 1, r = W, ans = W;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(mid)) {
            r = mid - 1;
            ans = mid;
        } else {
            l = mid + 1;
        }
    }
    cout << ans << '\n';
    return 0;   
}

Compilation message

watching.cpp: In function 'int32_t main()':
watching.cpp:56:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 908 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 1 ms 688 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 15964 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 170 ms 16164 KB Output is correct
4 Correct 173 ms 15960 KB Output is correct
5 Correct 160 ms 16184 KB Output is correct
6 Correct 166 ms 15964 KB Output is correct
7 Correct 171 ms 16168 KB Output is correct
8 Correct 165 ms 16228 KB Output is correct
9 Correct 163 ms 16176 KB Output is correct
10 Correct 173 ms 16180 KB Output is correct
11 Correct 166 ms 15964 KB Output is correct
12 Correct 186 ms 16164 KB Output is correct
13 Correct 156 ms 15964 KB Output is correct
14 Correct 154 ms 16168 KB Output is correct
15 Correct 150 ms 16172 KB Output is correct