oj.uz

Submission #1001969

# Submission time Handle Problem Language Result Execution time Memory
1001969 2024-06-19T08:52:34 Z vjudge1 Watching (JOI13_watching) C++17
100 / 100
 808 ms 64832 KB 
#pragma GCC optimize("Ofast")
#include"bits/stdc++.h"
 
#define int long long
 
using namespace std;
 
const int sz = 2e3 + 20;
const int inf = 1e18;
 
vector<vector<int>> aj[sz];
int nw[sz], nww[sz];
int n, p, q;
int vi[sz][sz];
int vs[sz][sz];
int a[sz];
bool f;
 
void dfs(int v, int cl, int cr) {
    vi[v][cl]=min(vi[v][cl], cr);
    vs[v][cr]=min(vs[v][cr], cl);
    if (cl > p || cr > q) return;
    if (v == n + 1) {
        f |= (cl <= p && cr <= q);
    } else {
        for (auto& u : aj[v]) {
            if(cr+u[2]>=vi[u[0]][cl+u[1]] || cl+u[1]>=vs[u[0]][cr+u[2]]) continue;
            if(u[1] <= nw[v] || u[2] <= nww[v]) {
                dfs(u[0], cl + u[1], cr + u[2]);
            }
            if (f) return;
        }
    }
}
 
bool che(int mi) {
    // map<vector<int>,bool>vi;
    for (int i = 1; i <= n; i ++) {
        aj[i].clear();
        int d = lower_bound(a + 1, a + n + 1, a[i] + mi) - &a[i];
        int c = lower_bound(a + 1, a + n + 1, a[i] + 2 * mi) - &a[i];
        aj[i].push_back({i + d, 1, 0});
        aj[i].push_back({i + c, 0, 1});
        nw[i] = nww[i] = inf;
    }
    fill_n(&vi[0][0], sz * sz, INT_MAX);
    fill_n(&vs[0][0], sz * sz, INT_MAX);
    f = false;
    dfs(1, 0, 0);
    return f;
}
 
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
 
    cin >> n >> p >> q;
 
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
    }
 
    sort(a + 1, a + n + 1);
    a[n + 1] = inf;

    int le, ri;
    le = 0, ri = (a[n] - a[1]) / (p + q) + 10;
    // cout << ri << '\n';
 
    while (1 < ri - le) {
        int mi = le + (ri - le) / 2;
 
        if (che(mi)) {
            ri = mi;
        } else {
            le = mi;
        }
    }
 
    cout << ri << '\n';
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 64388 KB Output is correct
2 Correct 31 ms 64360 KB Output is correct
3 Correct 101 ms 64348 KB Output is correct
4 Correct 59 ms 64340 KB Output is correct
5 Correct 57 ms 64348 KB Output is correct
6 Correct 56 ms 64348 KB Output is correct
7 Correct 99 ms 64384 KB Output is correct
8 Correct 96 ms 64348 KB Output is correct
9 Correct 100 ms 64388 KB Output is correct
10 Correct 92 ms 64388 KB Output is correct
11 Correct 96 ms 64244 KB Output is correct
12 Correct 137 ms 64352 KB Output is correct
13 Correct 58 ms 64376 KB Output is correct
14 Correct 76 ms 64340 KB Output is correct
15 Correct 85 ms 64348 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 64600 KB Output is correct
2 Correct 101 ms 64340 KB Output is correct
3 Correct 74 ms 64772 KB Output is correct
4 Correct 60 ms 64832 KB Output is correct
5 Correct 66 ms 64600 KB Output is correct
6 Correct 59 ms 64600 KB Output is correct
7 Correct 123 ms 64684 KB Output is correct
8 Correct 320 ms 64604 KB Output is correct
9 Correct 808 ms 64756 KB Output is correct
10 Correct 106 ms 64768 KB Output is correct
11 Correct 83 ms 64820 KB Output is correct
12 Correct 301 ms 64596 KB Output is correct
13 Correct 88 ms 64592 KB Output is correct
14 Correct 93 ms 64500 KB Output is correct
15 Correct 99 ms 64600 KB Output is correct