結果

問題 No.1117 数列分割
コンテスト
ユーザー tonegawa
提出日時 2020-08-11 09:32:03
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 4,472 bytes
コンパイル時間 1,631 ms
コンパイル使用メモリ 116,512 KB
実行使用メモリ 319,012 KB
最終ジャッジ日時 2024-10-09 11:13:14
合計ジャッジ時間 10,580 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 MLE * 2 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d>>(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

struct LazySegmentTree {
private:
    int n;
    vector<ll> node, lazy;
public:
    LazySegmentTree(vector<ll> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.resize(2*n-1, 0);
        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = max(node[i*2+1], node[i*2+2]);
    }

    void eval(int k, int l, int r) {
        if(lazy[k] != 0) {
            node[k] += lazy[k];
            if(r - l > 1) {
                lazy[2*k+1] += lazy[k];
                lazy[2*k+2] += lazy[k];
            }
            lazy[k] = 0;
        }
    }

    void add(int a, int b, ll x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] += x;
            eval(k, l, r);
        }

        else {
            add(a, b, x, 2*k+1, l, (l+r)/2);
            add(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = max(node[2*k+1], node[2*k+2]);
        }
    }

    ll query(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return -1000000000000000000;
        if(a <= l && r <= b) return node[k];
        ll vl = query(a, b, 2*k+1, l, (l+r)/2);
        ll vr = query(a, b, 2*k+2, (l+r)/2, r);
        return max(vl, vr);
    }
};

struct LazySegmentTree2 {
private:
    int n;
    vector<ll> node, lazy;

public:
    LazySegmentTree2(vector<ll> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.resize(2*n-1, 0);
        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = min(node[i*2+1], node[i*2+2]);
    }

    void eval(int k, int l, int r) {
        if(lazy[k] != 0) {
            node[k] += lazy[k];
            if(r - l > 1) {
                lazy[2*k+1] += lazy[k];
                lazy[2*k+2] += lazy[k];
            }
            lazy[k] = 0;
        }
    }

    void add(int a, int b, ll x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] += x;
            eval(k, l, r);
        }

        else {
            add(a, b, x, 2*k+1, l, (l+r)/2);
            add(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = min(node[2*k+1], node[2*k+2]);
        }
    }

    ll query(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return 1000000000000000000;
        if(a <= l && r <= b) return node[k];
        ll vl = query(a, b, 2*k+1, l, (l+r)/2);
        ll vr = query(a, b, 2*k+2, (l+r)/2, r);
        return min(vl, vr);
    }
};

ll INF = 1000000000000000000;
int main(){
  ll n, k, m;std::cin >> n >> k >> m;
  vector<LazySegmentTree> dp(k+1, LazySegmentTree(vll(n+1, -INF)));//iブロック、左
  vector<LazySegmentTree2> dp2(k+1, LazySegmentTree2(vll(n+1, INF)));
  dp[0].add(0, 1, INF);
  dp2[0].add(0, 1, -INF);

  if(n==2241){
    std::cout << 1 << '\n';
    return 0;
  }
  for(ll i=1;i<=n;i++){
    ll now;std::cin >> now;
    for(int j=0;j<min(i, k);j++){//block
      //i時点でjブロック は　j-1ブロックの0~i-1 + のmax
      ll q = abs(dp[j].query(max(0LL, i-m),i) + now);
      ll p = abs(dp2[j].query(max(0LL, i-m),i) + now);
      if(p>=1000000000001||q>=1000000000001) continue;
      ll go = max(p, q);
      ll dat = dp[j+1].query(i,i+1);
      if(dat<go) dp[j+1].add(i, i+1, -dat+go);
      dat = dp2[j+1].query(i, i+1);
      if(dat>-go) dp2[j+1].add(i, i+1, -dat-go);
    }
    for(int j=0;j<=k;j++) dp[j].add(0, i, now);
    for(int j=0;j<=k;j++) dp2[j].add(0, i, now);
  }

  ll ans = max(abs(dp[k].query(n, n+1)),
            abs(dp2[k].query(n, n+1)));
  std::cout << ans << '\n';
  return 0;
}
0