oj.uz

답안 #1001966

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1001966 2024-06-19T08:52:01 Z coolboy19521 구경하기 (JOI13_watching) C++17
50 / 100
 117 ms 63464 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

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 63068 KB Output is correct
2 Correct 27 ms 63068 KB Output is correct
3 Correct 95 ms 63068 KB Output is correct
4 Correct 56 ms 63196 KB Output is correct
5 Correct 58 ms 63056 KB Output is correct
6 Correct 55 ms 63064 KB Output is correct
7 Correct 95 ms 63192 KB Output is correct
8 Correct 91 ms 63092 KB Output is correct
9 Correct 93 ms 63064 KB Output is correct
10 Correct 90 ms 63196 KB Output is correct
11 Correct 86 ms 63068 KB Output is correct
12 Correct 81 ms 63064 KB Output is correct
13 Correct 53 ms 63068 KB Output is correct
14 Correct 67 ms 63068 KB Output is correct
15 Correct 69 ms 62992 KB Output is correct

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 117 ms 63464 KB Output isn't correct
2 Halted 0 ms 0 KB -