Contest Duration: ~ (local time) (120 minutes)

Submission #15083760

Source Code Expand

Copy
```// I SELL YOU...!
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using TP = tuple<ll,ll,ll>;
void init_io(){
cin.tie(0);
ios::sync_with_stdio(false);
cout << fixed << setprecision(18);
}
template <typename Monoid >
struct SegmentTree{
using F = function< Monoid(Monoid,Monoid) >;

int sz;
vector<Monoid> seg;

const F f;
const Monoid M;

SegmentTree(int n,const F f,const Monoid &M) : f(f),M(M){
sz = 1;
while(sz<n) sz<<=1;
seg.assign(sz*2,M);
}
void set(int k,const Monoid &v){
seg[k+sz] = v;
}
void build(){
for(int k=sz-1;k>0;k--){
seg[k] = f(seg[2*k],seg[2*k+1]);
}
}
void update(int k,const Monoid &v){
k += sz;
seg[k] = v;
while(k >>= 1){
seg[k] = f(seg[2*k],seg[2*k+1]);
}
}
Monoid que(int a,int b){
Monoid L=M,R=M;
for(a+=sz, b+=sz;a<b;a>>=1,b>>=1){
if(a&1) L = f(L,seg[a++]);
if(b&1) R = f(seg[--b],R);
}
return f(L,R);
}
Monoid operator[](const int &k) const{
return seg[k+sz];
}
};
ll MINF = -1e14;
signed main(){
init_io();
ll n,k;
cin >> n >> k;
vector<ll> b(n),dp(n+1,MINF);
for(int i=0;i<n;i++){
cin >> b[i];
}
dp[0] = 0;
SegmentTree<ll> seg(n+1,[](ll a,ll b){return max(a,b);},MINF);
seg.update(0,0);
for(int i=1;i<=n;i++){
dp[i] = max(dp[i-1]+b[i-1],dp[i]);
if(i-k>=0){
dp[i] = max(seg.que(0,i-k+1),dp[i]);
}
seg.update(i,dp[i]);
}
cout << dp[n]<<endl;
}
```

#### Submission Info

Submission Time 2020-07-08 18:59:08+0900 B - Neutralize shop_one C++ (GCC 9.2.1) 400 1704 Byte AC 64 ms 10592 KB

#### Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 a01, a02, a03, a04
All 400 / 400 a01, a02, a03, a04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, b25, b26, b27, b28, b29, b30, b31, b32, b33, b34, b35, b36, b37, b38, b39, b40, b41, b42, b43, b44
Case Name Status Exec Time Memory
a01 9 ms 3592 KB
a02 4 ms 3500 KB
a03 2 ms 3556 KB
a04 2 ms 3624 KB
b05 5 ms 3652 KB
b06 4 ms 3656 KB
b07 10 ms 3992 KB
b08 47 ms 10208 KB
b09 63 ms 10300 KB
b10 48 ms 10272 KB
b11 43 ms 10236 KB
b12 6 ms 3616 KB
b13 46 ms 10160 KB
b14 50 ms 10292 KB
b15 56 ms 10588 KB
b16 60 ms 10592 KB
b17 64 ms 10228 KB
b18 56 ms 10156 KB
b19 60 ms 10312 KB
b20 57 ms 9996 KB
b21 45 ms 10260 KB
b22 49 ms 10256 KB
b23 63 ms 10240 KB
b24 51 ms 9696 KB
b25 57 ms 10328 KB
b26 56 ms 10224 KB
b27 46 ms 10524 KB
b28 57 ms 10332 KB
b29 54 ms 10232 KB
b30 41 ms 6792 KB
b31 56 ms 10236 KB
b32 55 ms 10324 KB
b33 49 ms 9800 KB
b34 48 ms 9968 KB
b35 50 ms 10528 KB
b36 57 ms 10296 KB
b37 61 ms 10256 KB
b38 59 ms 10588 KB
b39 63 ms 10232 KB
b40 56 ms 10524 KB
b41 58 ms 10592 KB
b42 58 ms 10276 KB
b43 62 ms 10256 KB
b44 62 ms 10232 KB