結果
問題 | No.1247 ブロック登り |
ユーザー |
![]() |
提出日時 | 2020-10-02 23:30:45 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,539 ms / 3,000 ms |
コード長 | 3,046 bytes |
コンパイル時間 | 7,202 ms |
コンパイル使用メモリ | 264,420 KB |
最終ジャッジ日時 | 2025-01-15 01:22:28 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;using Int = long long;const char newl = '\n';template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}template<typename T=Int>vector<T> read(size_t n){vector<T> ts(n);for(size_t i=0;i<n;i++) cin>>ts[i];return ts;}template <typename E>struct SegmentTree{using H = function<E(E,E)>;Int n,height;H h;E ei;vector<E> laz;SegmentTree(H h,E ei):h(h),ei(ei){}void init(Int n_){n=1;height=0;while(n<n_) n<<=1,height++;laz.assign(2*n,ei);}inline void propagate(Int k){if(laz[k]==ei) return;laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);laz[k]=ei;}inline void thrust(Int k){for(Int i=height;i;i--) propagate(k>>i);}void update(Int a,Int b,E x){if(a>=b) return;thrust(a+=n);thrust(b+=n-1);for(Int l=a,r=b+1;l<r;l>>=1,r>>=1){if(l&1) laz[l]=h(laz[l],x),l++;if(r&1) --r,laz[r]=h(laz[r],x);}}E get_val(Int a){thrust(a+=n);return laz[a];}void set_val(Int a,E x){thrust(a+=n);laz[a]=x;}};//INSERT ABOVE HEREconst Int MAX = 303;const Int INF = 1e18;Int dp[MAX][2][MAX][MAX];signed main(){cin.tie(0);ios::sync_with_stdio(0);Int n,k;cin>>n>>k;auto as=read(n);vector<Int> ans(n);// start from parityfor(Int p=0;p<2;p++){// initfor(Int i=0;i<=k;i++)for(Int l=0;l<n;l++)for(Int r=0;r<n;r++)dp[i][0][l][r]=dp[i][1][l][r]=-INF;// [l, r]for(Int l=0;l+1<n;l++){Int r=l+1;if((abs(r-k)&1)==p) chmax(dp[k-1][0][l][r],as[l]*(k-1)+as[r]*(k-0));if((abs(l-k)&1)==p) chmax(dp[k-1][1][l][r],as[l]*(k-0)+as[r]*(k-1));}auto h=[&](Int a,Int b){return max(a,b);};SegmentTree<Int> seg(h,-INF);seg.init(n);for(Int i=k-1;i>=0;i--){for(Int l=0;l<n;l++){for(Int r=l+1;r<n;r++){// [l, r]if(dp[i][0][l][r]!=-INF)seg.update(l,min(l+i,r)+1,dp[i][0][l][r]);if(dp[i][1][l][r]!=-INF)seg.update(max(l,r-i),r+1,dp[i][1][l][r]);if(i==0) continue;if(dp[i][0][l][r]!=-INF){Int res=dp[i][0][l][r];// cout<<res<<endl;if(l>=1) chmax(dp[i-1][0][l-1][r],res+as[l-1]*(i-1));if(i>=2) chmax(dp[i-2][0][l][r],res);if((r-l)<=i) chmax(dp[i-(r-l)][1][l][r],res);}if(dp[i][1][l][r]!=-INF){Int res=dp[i][1][l][r];// cout<<res<<endl;if(r+1<n) chmax(dp[i-1][1][l][r+1],res+as[r+1]*(i-1));if(i>=2) chmax(dp[i-2][1][l][r],res);if((r-l)<=i) chmax(dp[i-(r-l)][0][l][r],res);}}}}for(Int i=p;i<n;i+=2) ans[i]=seg.get_val(i);}for(Int i=0;i<n;i++) cout<<ans[i]<<newl;return 0;}