oj.uz

Submission #219179

# Submission time Handle Problem Language Result Execution time Memory
219179 2020-04-04T06:10:39 Z balbit Watching (JOI13_watching) C++14
100 / 100
 850 ms 16248 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define SZ(x) (int)(x.size())
#define ALL(x) (x.begin(),x.end())
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S &&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define bug(...)
#define endl '\n'
#endif // BALBIT

const int maxn =  2004;

int n,p,q;
int a[maxn];
int pn[maxn], qn[maxn];
int dp[maxn][maxn];

bool ok(int w) {
    bug(w);
    int j = n-1;
    for (int i = n-1; i>=0; --i) {
        // pn records the last THING that it can reach
        while (a[j] - a[i] >= w) --j;
        pn[i] = j;
    }

    j = n-1;
    for (int i = n-1; i>=0; --i) {
        // qn records the last THING that it can reach
        while (a[j] - a[i] >= 2*w) --j;
        qn[i] = j;
    }
    pn[n] = qn[n] = n-1;
    for (int i = 0; i<maxn; ++i) fill(dp[i], dp[i]+ maxn, -0x3f3f3f3f);
    dp[0][0] = -1;
    for (int i = 0; i<=p; ++i) {
        for (int j = 0; j<=q; ++j) {
            if (i || j) {
                dp[i][j] = max(i?pn[dp[i-1][j]+1]:-1, j?qn[dp[i][j-1]+1]:-1);
            }
        }
    }
    bug(w,dp[p][q]);
    return dp[p][q] >=n-1;
}

signed main(){
    IOS();
    cin>>n>>p>>q;
    for (int i = 0; i<n; ++i) cin>>a[i];
    sort(a, a+n);
    p = min(p,n);
    q = min(q,n);
    int l = 1, r = 1e9+1;
    while (l!=r) {
        int mid = (l+r)/2;
        if (ok(mid)) {
            r = mid;
        }else{
            l = mid+1;
        }
    }
    cout<<l<<endl;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 16000 KB Output is correct
2 Correct 94 ms 16128 KB Output is correct
3 Correct 79 ms 16000 KB Output is correct
4 Correct 79 ms 16120 KB Output is correct
5 Correct 82 ms 16000 KB Output is correct
6 Correct 84 ms 16000 KB Output is correct
7 Correct 79 ms 16128 KB Output is correct
8 Correct 81 ms 16116 KB Output is correct
9 Correct 81 ms 16000 KB Output is correct
10 Correct 78 ms 15872 KB Output is correct
11 Correct 81 ms 16120 KB Output is correct
12 Correct 84 ms 16000 KB Output is correct
13 Correct 77 ms 16000 KB Output is correct
14 Correct 79 ms 16000 KB Output is correct
15 Correct 80 ms 16116 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 16128 KB Output is correct
2 Correct 82 ms 16000 KB Output is correct
3 Correct 518 ms 16128 KB Output is correct
4 Correct 112 ms 16120 KB Output is correct
5 Correct 113 ms 16128 KB Output is correct
6 Correct 850 ms 16248 KB Output is correct
7 Correct 80 ms 16128 KB Output is correct
8 Correct 97 ms 16128 KB Output is correct
9 Correct 100 ms 16128 KB Output is correct
10 Correct 113 ms 16128 KB Output is correct
11 Correct 114 ms 16128 KB Output is correct
12 Correct 265 ms 16128 KB Output is correct
13 Correct 79 ms 16128 KB Output is correct
14 Correct 80 ms 16144 KB Output is correct
15 Correct 80 ms 16128 KB Output is correct