oj.uz

Submission #946577

# Submission time Handle Problem Language Result Execution time Memory
946577 2024-03-14T18:57:28 Z VMaksimoski008 Watching (JOI13_watching) C++14
0 / 100
 59 ms 2136 KB 
#include <bits/stdc++.h>

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

vector<vector<vector<bool> > > dp(105, vector<vector<bool>>(105, vector<bool>(105)));

int main() {
    int n, p, q;
    cin >> n >> p >> q;

    p = min(n, p);
    q = min(n, q);

    vector<int> v(n+1);
    for(int i=1; i<=n; i++) cin >> v[i];
    sort(1+all(v));

    auto f = [&](int mid) {
        for(int i=0; i<=n; i++)
            for(int j=0; j<=p; j++)
                for(int k=0; k<=q; k++) dp[i][j][k] = 0;

        dp[0][0][0] = 1;

        for(int i=1; i<=n; i++) {
            for(int j=0; j<=p; j++) {
                for(int k=0; k<=q; k++) {
                    if(j) {
                        int l=1, r=i, pos=0;
                        while(l <= r) {
                            int m = (l + r) / 2;
                            if(v[i] - v[m] < mid) pos = m, r = m - 1;
                            else l = m + 1;
                        }
                        if(dp[pos-1][j-1][k]) dp[i][j][k] = 1;
                    }

                    if(k) {
                        int l=1, r=i, pos=0;
                        while(l <= r) {
                            int m = (l + r) / 2;
                            if(v[i] - v[m] < 2ll * mid) pos = m, r = m - 1;
                            else l = m + 1;
                        }
                        if(dp[pos-1][j][k-1]) dp[i][j][k] = 1;
                    }
                }
            }
        }

        for(int i=0; i<=p; i++)
            for(int j=0; j<=q; j++)
                if(dp[n][i][j]) return 1;
        return 0;
    };

    int l=0, r=1e9, ans = 1e9;
    while(l <= r) {
        int mid = (l + r) / 2;
        if(f(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }

    cout << ans << '\n';
    return 0;
}

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1112 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 2 ms 1116 KB Output is correct
4 Runtime error 59 ms 1876 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 2136 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -