oj.uz

Submission #146226

# Submission time Handle Problem Language Result Execution time Memory
146226 2019-08-22T22:36:16 Z osaaateiasavtnl Watching (JOI13_watching) C++14
100 / 100
 239 ms 32092 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
const int N = 2007, INF = 1e9 + 7;
int n, p, q;
int a[N], dp[N][N], r1[N], r2[N];
bool check(int m) {
    for (int i = 0; i < n; ++i) {
        r1[i] = i;
        while (r1[i] + 1 < n && a[r1[i] + 1] - a[i] + 1 <= m) ++r1[i];
        r2[i] = i;
        while (r2[i] + 1 < n && a[r2[i] + 1] - a[i] + 1 <= 2 * m) ++r2[i];
    }   
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) dp[i][j] = 0;
    for (int i = 0; i <= p; ++i) {
        for (int j = 0; j <= q; ++j) {
            if (dp[i][j] == n) return 1;
            dp[i + 1][j] = max(dp[i + 1][j], r1[dp[i][j]] + 1);
            dp[i][j + 1] = max(dp[i][j + 1], r2[dp[i][j]] + 1);
        }
    }
    return 0;
}
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> p >> q;
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a, a + n);
    p = min(p, n); q = min(q, n);
    int l = 0, r = INF;
    while (l < r - 1) { 
        int m = (l + r) >> 1;
        if (check(m)) r = m;
        else l = m;
    }   
    cout << r << '\n';
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 31864 KB Output is correct
2 Correct 161 ms 31992 KB Output is correct
3 Correct 163 ms 31864 KB Output is correct
4 Correct 144 ms 31928 KB Output is correct
5 Correct 151 ms 31992 KB Output is correct
6 Correct 151 ms 31864 KB Output is correct
7 Correct 168 ms 31992 KB Output is correct
8 Correct 166 ms 31864 KB Output is correct
9 Correct 156 ms 31992 KB Output is correct
10 Correct 150 ms 31864 KB Output is correct
11 Correct 174 ms 31928 KB Output is correct
12 Correct 201 ms 31864 KB Output is correct
13 Correct 201 ms 31864 KB Output is correct
14 Correct 155 ms 31864 KB Output is correct
15 Correct 158 ms 31864 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 31984 KB Output is correct
2 Correct 163 ms 31992 KB Output is correct
3 Correct 207 ms 31864 KB Output is correct
4 Correct 182 ms 31864 KB Output is correct
5 Correct 176 ms 31996 KB Output is correct
6 Correct 168 ms 31992 KB Output is correct
7 Correct 197 ms 32092 KB Output is correct
8 Correct 181 ms 31992 KB Output is correct
9 Correct 183 ms 31976 KB Output is correct
10 Correct 188 ms 31992 KB Output is correct
11 Correct 177 ms 31992 KB Output is correct
12 Correct 235 ms 31992 KB Output is correct
13 Correct 193 ms 31992 KB Output is correct
14 Correct 183 ms 31864 KB Output is correct
15 Correct 180 ms 31864 KB Output is correct