結果
問題 |
No.2139 K Consecutive Sushi
|
ユーザー |
|
提出日時 | 2022-12-11 23:41:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 82 ms / 2,000 ms |
コード長 | 937 bytes |
コンパイル時間 | 1,780 ms |
コンパイル使用メモリ | 168,376 KB |
実行使用メモリ | 9,216 KB |
最終ジャッジ日時 | 2024-11-27 19:54:36 |
合計ジャッジ時間 | 3,766 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> P; #define REP(i,n) for(ll i=0;i<ll(n);i++) ll a[200010]; #define T 200010 #define INF 1e18 ll n,N,tree[4*T]; void init(){ n=1; while(n<N) n*=2; REP(i,2*n) tree[i]=INF; } void update(ll k, ll a){ k=n-1+k; tree[k]=a; while(k>0){ k=(k-1)/2; tree[k]=min(tree[2*k+1], tree[2*k+2]); } } ll query(ll a, ll b, ll k, ll l, ll r){ if(r<=a || b<=l) return INF; if(a<=l && r<=b) return tree[k]; else return min(query(a,b,2*k+1,l,(l+r)/2),query(a,b,2*k+2,(l+r)/2,r)); } int main(void){ ll i; cin.tie(0); ios_base::sync_with_stdio(false); ll K; cin >> N >> K; ll S=0; for(i=1;i<=N;i++){ cin >> a[i]; S+=a[i]; } N++; init(); update(0,0); for(i=1;i<=N;i++){ ll mn=query(max(i-K,0LL),i,0,0,n); update(i,a[i]+mn); if(i==N){ cout << S-a[i]-mn << endl; return 0; } } return 0; }