oj.uz

Submission #666510

# Submission time Handle Problem Language Result Execution time Memory
666510 2022-11-28T20:02:22 Z ljuba Watching (JOI13_watching) C++17
100 / 100
 904 ms 15936 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
typedef vector<int> vi;
typedef vector<ll> vll;
 
typedef vector<vi> vvi;
typedef vector<vll> vvll;
 
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
typedef vector<pii> vpii;
typedef vector<pll> vpll;
 
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define fi first
#define se second
 
template<class T> bool ckmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<class T> bool ckmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}
 
namespace debug {
    void __print(int x) {cerr << x;}
    void __print(long long 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 string &x) {cerr << '\"' << x << '\"';}
    void __print(const char *x) {cerr << '\"' << x << '\"';}
    void __print(bool x) {cerr << (x ? "true" : "false");}
 
    template<typename T, typename V>
    void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
    template<typename T>
    void __print(const T &x) {int f = 0; cerr << '{'; for(auto z : x) cerr << (f++ ? "," : ""), __print(z); cerr << "}";}
    void _print() {cerr << "]\n";}
    template <typename T, typename... V>
    void _print(T t, V... v) {__print(t); if(sizeof...(v)) cerr << ", "; _print(v...);}
 
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m" << "LINE(" << __LINE__ << ") -> " << "[" << #x << "] = ["; _print(x); cerr << "\033[0m";
#else
#define dbg(x...)
#endif
}
 
using namespace debug;
 
const char nl = '\n';
 
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

void solve() {
    int n, p, q;
    cin >> n >> p >> q;

    vll v(n);
    for(auto &z : v) cin >> z;
    sort(all(v));

    if(n <= p + q) {
        cout << 1 << nl;
        return;
    }

    const int INF = 1e9 + 12;

    auto calc = [&](ll x) {
        vector<vector<bool>> dp(n + 1, vector<bool>(p + 1, false));
        vvi mini(n + 1, vi(p + 1, INF));

        dp[0][0] = true;
        mini[0][0] = 0;

        for(int i = 0; i < n; ++i) {
            for(int j = 0; j <= p; ++j) {
                if(!dp[i][j]) continue;

                if(j + 1 <= p) {
                    int gde = lower_bound(all(v), v[i] + x) - v.begin();
                    dp[gde][j + 1] = true;
                    ckmin(mini[gde][j + 1], mini[i][j]);
                }

                {
                    int gde = lower_bound(all(v), v[i] + 2 * x) - v.begin();
                    dp[gde][j] = true;
                    ckmin(mini[gde][j], mini[i][j] + 1);
                }
            }
        }

        for(int i = 0; i <= p; ++i) {
            if(!dp[n][i]) continue;
            if(mini[n][i] <= q) return true;
        }

        return false;
    };

    ll l = 1, r = 1e9 + 12;
    ll ans = -1;

    while(l <= r) {
        ll mid = l + (r - l) / 2;

        if(calc(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    cout << ans << nl;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int testCases = 1;
    //cin >> testCases;
    while(testCases--)
        solve();
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 2 ms 328 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 1 ms 328 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 596 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 10 ms 700 KB Output is correct
8 Correct 93 ms 1548 KB Output is correct
9 Correct 320 ms 6732 KB Output is correct
10 Correct 904 ms 15936 KB Output is correct
11 Correct 98 ms 1300 KB Output is correct
12 Correct 617 ms 8536 KB Output is correct
13 Correct 9 ms 596 KB Output is correct
14 Correct 13 ms 728 KB Output is correct
15 Correct 10 ms 704 KB Output is correct