結果
問題 | No.1117 数列分割 |
ユーザー |
![]() |
提出日時 | 2020-07-19 01:39:13 |
言語 | C++11 (gcc 13.3.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 2,011 bytes |
コンパイル時間 | 1,252 ms |
コンパイル使用メモリ | 95,940 KB |
実行使用メモリ | 387,712 KB |
最終ジャッジ日時 | 2024-12-14 22:38:42 |
合計ジャッジ時間 | 26,658 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 MLE * 8 |
ソースコード
#include <iostream>#include <cstdio>#include <cmath>#include <ctime>#include <cstdlib>#include <cassert>#include <vector>#include <list>#include <stack>#include <queue>#include <deque>#include <map>#include <set>#include <bitset>#include <string>#include <algorithm>#include <utility>#define llint long long#define inf 1e18#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)#define chmin(x, y) (x) = min((x), (y))#define chmax(x, y) (x) = max((x), (y))#define mod 998244353using namespace std;typedef pair<llint, llint> P;struct SegTree{int size;vector<llint> seg;SegTree(){}SegTree(int size){this->size = size;seg.resize(1<<(size+1));}void init(){for(int i = 0; i < (1<<(size+1)); i++) seg[i] = -inf;}void update(int i, llint val){i += (1 << size);seg[i] = val;while(i > 1){i /= 2;seg[i] = max(seg[i*2], seg[i*2+1]);}}llint query(int a, int b, int k, int l, int r){if(b < l || r < a) return -inf;if(a <= l && r <= b) return seg[k];llint lval = query(a, b, k*2, l, (l+r)/2);llint rval = query(a, b, k*2+1, (l+r)/2+1, r);return max(lval, rval);}llint query(int a, int b){return query(a, b, 1, 0, (1<<size)-1);}};llint n, k, m;SegTree seg[3005], seg2[3005];llint a[3005], sum[3005];int main(void){ios::sync_with_stdio(0);cin.tie(0);cin >> n >> k >> m;for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 1; i <= n; i++) sum[i] = sum[i-1] + a[i];for(int i = 0; i <= k; i++){seg[i] = SegTree(12), seg[i].init();seg2[i] = SegTree(12), seg2[i].init();}seg[0].update(0, 0), seg2[0].update(0, 0);for(int i = 1; i <= k; i++){for(int j = 1; j <= n; j++){llint tmp = max(sum[j]+seg[i-1].query(max(0LL, j-m), j-1), -sum[j]+seg2[i-1].query(max(0LL, j-m), j-1));seg[i].update(j, tmp-sum[j]);seg2[i].update(j, tmp+sum[j]);}}cout << seg[k].query(n, n) + sum[n] << endl;return 0;}