oj.uz

Submission #882282

# Submission time Handle Problem Language Result Execution time Memory
882282 2023-12-02T22:47:47 Z noompty Watching (JOI13_watching) C++17
100 / 100
 197 ms 16220 KB 
#include <iostream>
#include <vector>
#include <tuple>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <cmath>
#include <array>
#include <random>
#include <string>
#include <cassert>
#include <climits>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
using namespace std;
 
#define ll long long
#define f first
#define s second
 
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
 
template<typename A> void __print(const A &x);
template<typename A, typename B> void __print(const pair<A, B> &p);
template<typename... A> void __print(const tuple<A...> &t);
template<typename T> void __print(stack<T> s);
template<typename T> void __print(queue<T> q);
template<typename T, typename... U> void __print(priority_queue<T, U...> q);
 
template<typename A> void __print(const A &x) {
    bool first = true;
    cerr << '{';
    for (const auto &i : x) {
        cerr << (first ? "" : ","), __print(i);
        first = false;
    }
    cerr << '}';
}
 
template<typename A, typename B> void __print(const pair<A, B> &p) {
    cerr << '(';
    __print(p.f);
    cerr << ',';
    __print(p.s);
    cerr << ')';
}
 
template<typename... A> void __print(const tuple<A...> &t) {
    bool first = true;
    cerr << '(';
    apply([&first] (const auto &...args) { ((cerr << (first ? "" : ","), __print(args), first = false), ...); }, t);
    cerr << ')';
}
 
template<typename T> void __print(stack<T> s) {
    vector<T> debugVector;
    while (!s.empty()) {
        T t = s.top();
        debugVector.push_back(t);
        s.pop();
    }
    reverse(debugVector.begin(), debugVector.end());
    __print(debugVector);
}
 
template<typename T> void __print(queue<T> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.front();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
 
template<typename T, typename... U> void __print(priority_queue<T, U...> q) {
    vector<T> debugVector;
    while (!q.empty()) {
        T t = q.top();
        debugVector.push_back(t);
        q.pop();
    }
    __print(debugVector);
}
 
void _print() { cerr << "]\n"; }
 
template <typename Head, typename... Tail> void _print(const Head &H, const Tail &...T) {
    __print(H);
    if (sizeof...(T)) cerr << ", ";
    _print(T...);
}
 
#ifdef DEBUG
	#define D(...) cerr << "Line: " << __LINE__ << " [" << #__VA_ARGS__ << "] = ["; _print(__VA_ARGS__)
#else
	#define D(...)
#endif

int n, p, q, l, r, dp[2005][2005];
vector<int> events;

bool valid(int x) {
    fill(&dp[0][0], &dp[0][0] + sizeof(dp) / sizeof(dp[0][0]), 2e9);
    dp[0][0] = 0;
    for (int i = 1, idx1, idx2; i <= n; i++) {
        idx1 = lower_bound(events.begin(), events.end(), events[i] + x) - events.begin() - 1;
        idx2 = lower_bound(events.begin(), events.end(), events[i] + 2 * x) - events.begin() - 1;
        for (int j = 0; j <= p; j++) {
            dp[idx1][j + 1] = min(dp[idx1][j + 1], dp[i - 1][j]);
            dp[idx2][j] = min(dp[idx2][j], dp[i - 1][j] + 1);
        }
    }
    for (int i = 0; i <= p; i++) {
        if (dp[n][i] <= q) return true;
    }
    return false;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> p >> q;
    events.push_back(INT_MIN);
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        events.push_back(x);
    }

    sort(events.begin(), events.end());

    if (p + q >= n) {
        cout << 1 << "\n";
        exit(0);
    }

    l = 0, r = 1e9;
    while (l + 1 != r) {
        int m = (l + r) / 2; 
        if (valid(m)) r = m;
        else l = m;
    }

    cout << r << "\n";

}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 15960 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 44 ms 16160 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 45 ms 16180 KB Output is correct
8 Correct 41 ms 15964 KB Output is correct
9 Correct 46 ms 16172 KB Output is correct
10 Correct 43 ms 16164 KB Output is correct
11 Correct 43 ms 15968 KB Output is correct
12 Correct 49 ms 15964 KB Output is correct
13 Correct 44 ms 15964 KB Output is correct
14 Correct 42 ms 16012 KB Output is correct
15 Correct 46 ms 16212 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 15964 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 47 ms 16036 KB Output is correct
8 Correct 56 ms 15964 KB Output is correct
9 Correct 104 ms 15960 KB Output is correct
10 Correct 197 ms 15960 KB Output is correct
11 Correct 54 ms 15964 KB Output is correct
12 Correct 124 ms 15964 KB Output is correct
13 Correct 48 ms 15960 KB Output is correct
14 Correct 59 ms 16220 KB Output is correct
15 Correct 53 ms 16216 KB Output is correct