Submission #1101950

#TimeUsernameProblemLanguageResultExecution timeMemory
1101950tsengangWatching (JOI13_watching)C++14
0 / 100
398 ms32004 KiB
#include <bits/stdc++.h> #define ll long long #define ff first #define ss second #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() using namespace std; ll n,q,k; struct segtree{ int n; vector<ll>d; segtree(ll n){ d.resize(4*n); build(1,1,n); } void build(ll v,ll l,ll r){ if(l==r){ d[v]=0; return; } ll m=(l+r)/2; build(v*2,l,m); build(v*2+1,m+1,r); d[v]=d[v*2]+d[v*2+1]; } ll query(ll v,ll l,ll r,ll L,ll R){ if(L>R||l>R||L>r) return 0; if(L<=l&&r<=R){ return d[v]; } ll m=(l+r)/2; return query(v*2,l,m,L,R)+query(v*2+1,m+1,r,L,R); } void update(ll v,ll l,ll r,ll pos,ll val){ if(pos<l||r<pos) return; if(l==r){ d[v]=val; return; } ll m=(l+r)/2; update(v*2,l,m,pos,val); update(v*2+1,m+1,r,pos,val); d[v]=d[v*2]+d[v*2+1]; } void updater(ll node, ll L, ll R, ll l, ll r, ll val){ if (L > R || L > r || R < l) return; if (L == R){ d[node] /= val; return; } ll mid = (L + R) / 2; updater(node*2, L, mid, l, r, val); updater(node*2 + 1, mid + 1, R, l, r, val); d[node] = d[node*2] + d[node*2+1]; } void update2(ll v,ll l,ll r,ll pos){ if(pos<l||r<pos) return; if(l==r){ d[v]/=k; return; } ll m=(l+r)>>1; update2(v*2,l,m,pos); update2(v*2+1,m+1,r,pos); d[v]=d[v*2]+d[v*2+1]; } }; ll dp[2005][2005]; int main() { ll n,p,q; cin >> n >> p >> q; p = min(p,n); q = min(q,n); ll a[n]; for(ll i = 1; i <= n; i++)cin >> a[i]; sort(a,a+n); ll x[2005],y[2005] ; ll l = 0,r = 1000000000; while(l < r){ ll w = (l+r)/2; memset(dp,0,sizeof dp); for(ll i = 1, j = 1; i <= n; i++) { while(a[j] - a[i] < w && j <= n) ++j; x[i] = --j; } for(ll i = 1, j = 1; i <= n; i++) { while(a[j] - a[i] < w+w && j <= n) ++j; y[i] = --j; } x[n+1] = y[n+1] = n; for(ll i = 0; i <= p; i++){ for(ll j = 0 ; j <= q; j++){ if(i < p)dp[i+1][j] = max(dp[i+1][j],x[dp[i][j]+1]); if(j < q)dp[i][j+1] = max(dp[i][j+1],y[dp[i][j]+1]); } } if(dp[p][q]>= n){ r = w; } else l = w+1; } cout << (l+r)/2; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...