結果
問題 |
No.1117 数列分割
|
ユーザー |
👑 ![]() |
提出日時 | 2021-01-04 15:42:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,107 ms / 3,000 ms |
コード長 | 947 bytes |
コンパイル時間 | 2,433 ms |
コンパイル使用メモリ | 207,276 KB |
最終ジャッジ日時 | 2025-01-17 09:36:06 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include<bits/stdc++.h> using namespace std; using LL=long long; using ULL=unsigned long long; #define rep(i,n) for(int i=0; i<(n); i++) const LL INF=1000000000000000; int N,K,M; LL A[2][3001]; LL dp[2][3001][3001]; deque<int> dpw[2][3001]; int main(){ cin>>N>>K>>M; rep(i,N) cin>>A[0][i]; A[0][N]=0; for(int i=N-1; i>=0; i--) A[0][i]+=A[0][i+1]; rep(i,N+1) A[1][i]=-A[0][i]; rep(t,2) rep(i,N+1) rep(k,K+1) dp[t][k][i]=-INF; rep(t,2) dp[t][0][0]=A[t][0]; rep(t,2) rep(k,K+1) dpw[t][k]={0}; rep(i,N) rep(k,K){ LL tmp = -INF; rep(t,2){ if(dpw[t][k].size()) if(dpw[t][k].front()<=i-M) dpw[t][k].pop_front(); if(dpw[t][k].size()) tmp=max(tmp,dp[t][k][dpw[t][k].front()]-A[t][i+1]); } rep(t,2){ dp[t][k+1][i+1]=tmp+A[t][i+1]; while(dpw[t][k+1].size()) if(dp[t][k+1][dpw[t][k+1].back()]<=dp[t][k+1][i+1]) dpw[t][k+1].pop_back(); else break; dpw[t][k+1].push_back(i+1); } } cout<<dp[0][K][N]<<endl; return 0; }