oj.uz

Submission #51430

# Submission time Handle Problem Language Result Execution time Memory
51430 2018-06-18T02:02:28 Z Flying_dragon_02 Watching (JOI13_watching) C++14
100 / 100
 448 ms 32252 KB 
#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int,int> ii;

long long l,r,n,p,q,dp[2005][2005],nxt[2005][3],a[2005];
vector<long long> vec;

bool check(long long w){
    a[n+1] = a[n];
    for(int i = 0;i<=n+1;i++){
        for(int j = 0;j<=1;j++){
            long long cost;
            if(j == 0)
                cost = w-1;
            else
                cost = 2*w-1;
            int it = upper_bound(vec.begin(),vec.end(),a[i]+cost) - vec.begin() - 1;
            nxt[i][j] = it;
        }
    }

    memset(dp,0,sizeof(dp));
    for(int i = 0;i<=p;i++){
        for(int j = 0;j<=q;j++){
            if(i>=1)
                dp[i][j] = nxt[dp[i-1][j]+1][0];
            if(j>=1)
                dp[i][j] = max(dp[i][j],nxt[dp[i][j-1]+1][1]);
        }
    }
    if(dp[p][q]>=n)
        return 1;
    else
        return 0;
}
int main(){
    cin.tie(0),ios::sync_with_stdio(0);
    cin >> n >> p >> q;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
        vec.pb(a[i]);
    }
    sort(a+1,a+1+n);
    vec.pb(-1);
    sort(vec.begin(),vec.end());
    if(p+q>=n){
        cout<<"1\n";
        return 0;
    }
    l = 1;
    r = 1e9;
    while(l<r){
        long long mid = (l+r)/2;
        if(check(mid))
            r = mid;
        else
            l = mid+1;
    }
    cout<<l;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 31864 KB Output is correct
2 Correct 2 ms 31864 KB Output is correct
3 Correct 212 ms 31976 KB Output is correct
4 Correct 2 ms 31976 KB Output is correct
5 Correct 2 ms 31976 KB Output is correct
6 Correct 2 ms 31976 KB Output is correct
7 Correct 210 ms 32044 KB Output is correct
8 Correct 207 ms 32044 KB Output is correct
9 Correct 204 ms 32144 KB Output is correct
10 Correct 213 ms 32144 KB Output is correct
11 Correct 224 ms 32228 KB Output is correct
12 Correct 226 ms 32228 KB Output is correct
13 Correct 226 ms 32232 KB Output is correct
14 Correct 224 ms 32232 KB Output is correct
15 Correct 217 ms 32240 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 32240 KB Output is correct
2 Correct 2 ms 32240 KB Output is correct
3 Correct 3 ms 32240 KB Output is correct
4 Correct 3 ms 32240 KB Output is correct
5 Correct 3 ms 32240 KB Output is correct
6 Correct 3 ms 32240 KB Output is correct
7 Correct 234 ms 32240 KB Output is correct
8 Correct 268 ms 32240 KB Output is correct
9 Correct 302 ms 32240 KB Output is correct
10 Correct 281 ms 32252 KB Output is correct
11 Correct 276 ms 32252 KB Output is correct
12 Correct 448 ms 32252 KB Output is correct
13 Correct 243 ms 32252 KB Output is correct
14 Correct 242 ms 32252 KB Output is correct
15 Correct 247 ms 32252 KB Output is correct