oj.uz

Submission #320222

# Submission time Handle Problem Language Result Execution time Memory
320222 2020-11-08T01:49:04 Z zaneyu Watching (JOI13_watching) C++14
100 / 100
 656 ms 16256 KB 
/*input
3 1 1
2
11
17
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;
#define ld double
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
const ll maxn=2e3+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=ll(1e9+7);
const ld PI=acos(-1);
const ld eps=1e-9;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
ll mult(ll a,ll b){
    return (a*b)%MOD;
}
ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=mult(res,a);
        a=mult(a,a);
        b>>=1;
    }
    return res;
}
int n,p,q;
int arr[maxn];
int dp[maxn][maxn];
bool wk(int w){
    FILL(dp,0);
    int p1=0,p2=0;
    REP(i,n){
        REP(j,q+1){
            if(i==0 and j==0){
                dp[i][j]=1;
                continue;
            }
            else if(i==0) dp[i][j]=0;
            else{
                while(arr[p1]<arr[i]-w+1) ++p1;
                while(arr[p2]<arr[i]-2*w+1) ++p2;
                dp[i][j]=INF;
                if(p1>0){
                    dp[i][j]=dp[p1-1][j]+1;
                }
                else dp[i][j]=1;
                if(j>0 and p2>0){
                    MNTO(dp[i][j],dp[p2-1][j-1]);
                }
                else if(p2==0 and j>0){
                    dp[i][j]=0;
                 //cout<<p1<<' '<<p2<<' '<<dp[i][j]<<' ';
                }
            }
        }
         //cout<<'\n';
    }
    if(dp[n-1][q]<=p) return true;
    return false; 
}
int main(){
    cin>>n>>p>>q;
    if(p+q>=n){
        cout<<1;
        return 0;
    }
    REP(i,n) cin>>arr[i];
    sort(arr,arr+n);
    ll l=2,r=2e9;
    while(l<r){
        //cout<<l<<' '<<r<<'\n';
        int mid=(l+r)/2;
        if(wk(mid)) r=mid;
        else l=mid+1;
    }
    cout<<l;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 16108 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 69 ms 16224 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 69 ms 16108 KB Output is correct
8 Correct 71 ms 16240 KB Output is correct
9 Correct 72 ms 16236 KB Output is correct
10 Correct 72 ms 16108 KB Output is correct
11 Correct 71 ms 16232 KB Output is correct
12 Correct 73 ms 16256 KB Output is correct
13 Correct 71 ms 16104 KB Output is correct
14 Correct 70 ms 16228 KB Output is correct
15 Correct 71 ms 16108 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 16252 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 79 ms 16108 KB Output is correct
8 Correct 317 ms 16228 KB Output is correct
9 Correct 113 ms 16228 KB Output is correct
10 Correct 102 ms 16108 KB Output is correct
11 Correct 656 ms 16108 KB Output is correct
12 Correct 382 ms 16108 KB Output is correct
13 Correct 80 ms 16252 KB Output is correct
14 Correct 77 ms 16108 KB Output is correct
15 Correct 81 ms 16228 KB Output is correct