Submission #523583

#	Time	Username	Problem	Language	Result	Execution time	Memory
523583		inluminas	K blocks (IZhO14_blocks)	C++17	0 / 100	1 ms	204 KiB

blocks

#include"bits/stdc++.h"
using namespace std;
 
#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX

const ll lmt=1e5+10;
ll mx[4*lmt],pre[lmt];

void update(ll at,ll L,ll R,ll pos,ll val){
  if(L==R){
    mx[at]=val;
    return;
  }
  ll mid=(L+R)>>1;
  if(pos<=mid) update(at*2,L,mid,pos,val);
  else update(at*2+1,mid+1,R,pos,val);
  mx[at]=max(mx[at*2],mx[at*2+1]);
}

ll query(ll at,ll L,ll R,ll l,ll r){
  if(r<L || R<l || r<l) return 0;
  if(l<=L && R<=r) return mx[at];
  ll mid=(L+R)>>1;
  ll x=query(at*2,L,mid,l,r),y=query(at*2+1,mid+1,R,l,r);
  return max(x,y);
}

int main(){
  fastio;

  ll n,k;
  cin>>n>>k;
  for(ll i=1;i<=n;i++){
    ll x;
    cin>>x;
    update(1,1,n,i,x);
    pre[i]=pre[i-1]+x;
  }
  ll ans=inf;
  for(ll i=0;i<=k-1;i++){
    ll tot=pre[i]+pre[n]-pre[n-k+1+i]+query(1,1,n,i+1,n-k+1+i);
    ans=min(ans,tot);
  }
  cout<<ans<<endl;
  return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 18
• Subtask 3: 0 / 21
• Subtask 4: 0 / 47