oj.uz

Submission #1001965

# Submission time Handle Problem Language Result Execution time Memory
1001965 2024-06-19T08:51:41 Z vjudge1 Watching (JOI13_watching) C++17
50 / 100
 107 ms 63320 KB 
#pragma GCC optimize("Ofast")
#include"bits/stdc++.h"
 
#define int long long
 
using namespace std;
 
const int sz = 2e3 + 1;
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 106 ms 63192 KB Output is correct
2 Correct 25 ms 63064 KB Output is correct
3 Correct 100 ms 63068 KB Output is correct
4 Correct 57 ms 63068 KB Output is correct
5 Correct 54 ms 63200 KB Output is correct
6 Correct 52 ms 63068 KB Output is correct
7 Correct 95 ms 63136 KB Output is correct
8 Correct 91 ms 63068 KB Output is correct
9 Correct 89 ms 63196 KB Output is correct
10 Correct 82 ms 63068 KB Output is correct
11 Correct 92 ms 63064 KB Output is correct
12 Correct 86 ms 63060 KB Output is correct
13 Correct 52 ms 63068 KB Output is correct
14 Correct 55 ms 63064 KB Output is correct
15 Correct 69 ms 63200 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 107 ms 63320 KB Output isn't correct
2 Halted 0 ms 0 KB -