結果
問題 | No.2139 K Consecutive Sushi |
ユーザー | tko919 |
提出日時 | 2022-12-03 00:26:47 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 51 ms / 2,000 ms |
コード長 | 6,483 bytes |
コンパイル時間 | 2,102 ms |
コンパイル使用メモリ | 210,236 KB |
実行使用メモリ | 22,284 KB |
最終ジャッジ日時 | 2024-11-27 19:48:07 |
合計ジャッジ時間 | 4,034 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 51 ms
22,168 KB |
testcase_04 | AC | 51 ms
22,284 KB |
testcase_05 | AC | 50 ms
22,144 KB |
testcase_06 | AC | 50 ms
22,064 KB |
testcase_07 | AC | 50 ms
22,144 KB |
testcase_08 | AC | 41 ms
22,096 KB |
testcase_09 | AC | 44 ms
22,144 KB |
testcase_10 | AC | 47 ms
22,144 KB |
testcase_11 | AC | 45 ms
22,052 KB |
testcase_12 | AC | 39 ms
22,108 KB |
testcase_13 | AC | 2 ms
5,248 KB |
testcase_14 | AC | 2 ms
5,248 KB |
testcase_15 | AC | 2 ms
5,248 KB |
testcase_16 | AC | 2 ms
5,248 KB |
testcase_17 | AC | 2 ms
5,248 KB |
testcase_18 | AC | 2 ms
5,248 KB |
testcase_19 | AC | 2 ms
5,248 KB |
testcase_20 | AC | 2 ms
5,248 KB |
testcase_21 | AC | 2 ms
5,248 KB |
testcase_22 | AC | 2 ms
5,248 KB |
testcase_23 | AC | 6 ms
5,248 KB |
testcase_24 | AC | 17 ms
8,960 KB |
testcase_25 | AC | 34 ms
17,024 KB |
testcase_26 | AC | 6 ms
5,376 KB |
testcase_27 | AC | 14 ms
8,192 KB |
testcase_28 | AC | 16 ms
8,448 KB |
testcase_29 | AC | 8 ms
5,760 KB |
testcase_30 | AC | 20 ms
10,496 KB |
testcase_31 | AC | 44 ms
20,352 KB |
testcase_32 | AC | 9 ms
5,888 KB |
testcase_33 | AC | 47 ms
22,068 KB |
ソースコード
#line 1 "library/Template/template.hpp"#include <bits/stdc++.h>using namespace std;#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)#define ALL(v) (v).begin(),(v).end()using ll=long long int;const int inf = 0x3fffffff;const ll INF = 0x1fffffffffffffff;template<typename T>inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}template<typename T>inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}#line 2 "library/Utility/fastio.hpp"#include <unistd.h>class FastIO{static constexpr int L=1<<16;char rdbuf[L];int rdLeft=0,rdRight=0;inline void reload(){int len=rdRight-rdLeft;memmove(rdbuf,rdbuf+rdLeft,len);rdLeft=0,rdRight=len;rdRight+=fread(rdbuf+len,1,L-len,stdin);}inline bool skip(){for(;;){while(rdLeft!=rdRight and rdbuf[rdLeft]<=' ')rdLeft++;if(rdLeft==rdRight){reload();if(rdLeft==rdRight)return false;}else break;}return true;}template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline bool _read(T& x){if(!skip())return false;if(rdLeft+20>=rdRight)reload();bool neg=false;if(rdbuf[rdLeft]=='-'){neg=true;rdLeft++;}x=0;while(rdbuf[rdLeft]>='0' and rdLeft<rdRight){x=x*10+(neg?-(rdbuf[rdLeft++]^48):(rdbuf[rdLeft++]^48));}return true;}template<typename T,enable_if_t<is_floating_point<T>::value,int> =0>inline bool _read(T& x){if(!skip())return false;if(rdLeft+20>=rdRight)reload();bool neg=false;if(rdbuf[rdLeft]=='-'){neg=true;rdLeft++;}x=0;while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){x=x*10+(rdbuf[rdLeft++]^48);}if(rdbuf[rdLeft]!='.')return true;rdLeft++;T base=.1;while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft<rdRight){x+=base*(rdbuf[rdLeft++]^48);base*=.1;}if(neg)x=-x;return true;}inline bool _read(char& x){if(!skip())return false;if(rdLeft+1>=rdRight)reload();x=rdbuf[rdLeft++];return true;}inline bool _read(string& x){if(!skip())return false;for(;;){int pos=rdLeft;while(pos<rdRight and rdbuf[pos]>' ')pos++;x.append(rdbuf+rdLeft,pos-rdLeft);if(rdLeft==pos)break;rdLeft=pos;if(rdLeft==rdRight)reload();else break;}return true;}template<typename T>inline bool _read(vector<T>& v){for(auto& x:v){if(!_read(x))return false;}return true;}char wtbuf[L],tmp[50];int wtRight=0;inline void flush(){fwrite(wtbuf,1,wtRight,stdout);wtRight=0;}inline void _write(const char& x){if(wtRight>L-32)flush();wtbuf[wtRight++]=x;}inline void _write(const string& x){for(auto& c:x)_write(c);}template<typename T,enable_if_t<is_integral<T>::value,int> =0>inline void _write(T x){if(wtRight>L-32)flush();if(x==0){_write('0');return;}else if(x<0){_write('-');if (__builtin_expect(x == std::numeric_limits<T>::min(), 0)) {switch (sizeof(x)) {case 2: _write("32768"); return;case 4: _write("2147483648"); return;case 8: _write("9223372036854775808"); return;}}x=-x;}int pos=0;while(x!=0){tmp[pos++]=char((x%10)|48);x/=10;}rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i];wtRight+=pos;}template<typename T>inline void _write(const vector<T>& v){rep(i,0,v.size()){if(i)_write(' ');_write(v[i]);}}public:FastIO(){}~FastIO(){flush();}inline void read(){}template <typename Head, typename... Tail>inline void read(Head& head,Tail&... tail){assert(_read(head));read(tail...);}template<bool ln=true,bool space=false>inline void write(){if(ln)_write('\n');}template <bool ln=true,bool space=false,typename Head, typename... Tail>inline void write(const Head& head,const Tail&... tail){if(space)_write(' ');_write(head);write<ln,true>(tail...);}};/*** @brief Fast IO*/#line 3 "sol.cpp"#line 2 "library/DataStructure/segtree.hpp"template<typename M,typename N,M (*f)(M,M),M (*g)(M,N),M (*m1)()>struct SegmentTree{int n; vector<M> data;SegmentTree(int _n=0){n=1; while(n<_n)n<<=1; data.assign(2*n,m1());}void run(vector<M>& v){for(int i=0;i<(int)v.size();i++)data[i+n]=v[i];for(int k=n-1;k>0;k--)data[k]=f(data[2*k],data[2*k+1]);}void set(int k,const M &x){k+=n; data[k]=x;while(k>>=1)data[k]=f(data[2*k],data[2*k+1]);}void update(int k,const N &x){k+=n; data[k]=g(data[k],x);while(k>>=1)data[k]=f(data[2*k],data[2*k+1]);}M query(int a,int b){M L=m1(),R=m1();for(a+=n,b+=n;a<b;a>>=1,b>>=1){if(a&1)L=f(L,data[a++]);if(b&1)R=f(data[--b],R);}return f(L,R);}M operator[](const int &k)const{return data[k+n];}};/*** @brief Segment Tree*/#line 5 "sol.cpp"ll f(ll a,ll b){return max(a,b);}ll g(ll a,ll b){return a+b;}ll e0(){return -INF;}FastIO io;int main(){int n,k;io.read(n,k);vector<int> a(n);io.read(a);// dp[i][j]:=i番目まで見た時のmax,j:i番目をとったか?// dp[i][0]=max(dp[i-1][0],dp[i-1][1])// dp[i][1]=max_{i-j<k}dp[j][0]-rui[j]+rui[i]vector<ll> tmp(n+1),rui(n+1);rep(i,0,n)rui[i+1]=rui[i]+a[i];vector dp(n+1,vector<ll>(2));SegmentTree<ll,ll,f,g,e0> seg(n+1);seg.run(tmp);rep(i,0,n){dp[i+1][0]=max(dp[i][0],dp[i][1]);dp[i+1][1]=seg.query(max(i-k+2,0),i+1);dp[i+1][1]+=rui[i+1];seg.update(i+1,dp[i+1][0]-rui[i+1]);}// io.write(rui);ll ret=max(dp[n][0],dp[n][1]);io.write(ret);return 0;}