Submission #523582

#TimeUsernameProblemLanguageResultExecution timeMemory
523582inluminasK개의 묶음 (IZhO14_blocks)C++17
0 / 100
1 ms332 KiB
#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 int lmt=1e5+10;
int mx[4*lmt],pre[lmt];

void update(int at,int L,int R,int pos,int val){
  if(L==R){
    mx[at]=val;
    return;
  }
  int 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]);
}

int query(int at,int L,int R,int l,int r){
  if(r<L || R<l || r<l) return 0;
  if(l<=L && R<=r) return mx[at];
  int mid=(L+R)>>1;
  int 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;

  int n,k;
  cin>>n>>k;
  for(int i=1;i<=n;i++){
    int x;
    cin>>x;
    update(1,1,n,i,x);
    pre[i]=pre[i-1]+x;
  }
  ll ans=inf;
  for(int 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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...