結果

問題 No.8103 Range Chmax and Maximize Abs Sum
コンテスト
ユーザー Kude
提出日時 2023-03-31 22:40:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,744 bytes
コンパイル時間 2,640 ms
コンパイル使用メモリ 226,864 KB
最終ジャッジ日時 2025-02-11 21:14:03
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 16 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;

template<class Int = int, class Long = long long>
struct CHT {
    static const Int IntMax = std::numeric_limits<Int>::max() / 2 - 1;
    static const Int IntMin = std::numeric_limits<Int>::min() / 2 + 1;
    using P = std::pair<Int, Int>;
    struct Line { Int a, b; };
    struct Segment { Int b, l, r; };
    std::map<Int, Segment> segs; // maps slopes to segments
    std::map<Int, Line> ends; // maps x-coordinates to lines

    // y = ax+b = cx+d, a<c
    // x = (b-d)/(c-a), y = (bc-ad)/(c-a)
    // ex+f<=y <=> e(b-d)+f(c-a)<=bc-ad

    Int ceiling(Int a, Int b) {
        assert(b > 0);
        return a > 0 ? (a - 1) / b + 1 : a / b;
    }
    // returns ceiling of x
    // y=ax+b=cx+d
    Int intersection_x(Int a, Int b, Int c, Int d) {
        assert(a <= c);
        if (a == c) return b > d ? IntMax : IntMin;
        return ceiling(b - d, c - a);
    }

    // query x must be between [IntMin, IntMax)
    void add_line(Int a, Int b) {
        assert(IntMin <= a && a < IntMax);
        assert(IntMin <= b && b < IntMax);
        Int l = IntMin, r = IntMax;
        auto it = segs.lower_bound(a);
        auto it_x = it == segs.end() ? ends.end() : ends.find(it->second.r);
        while(it != segs.end()) {
            const Int& a_it = it->first;
            auto& [b_it, l_it, r_it] = it->second;
            Int x = intersection_x(a, b, a_it, b_it);
            if (x >= r_it) {
                it = segs.erase(it);
                it_x = ends.erase(it_x);
            } else {
                r = x;
                if (x > l_it) {
                    l_it = x;
                }
                break;
            }
        }
        while(it != segs.begin()) {
            auto pit = std::prev(it);
            auto pit_x = std::prev(it_x);
            const Int& a_it = pit->first;
            auto& [b_it, l_it, r_it] = pit->second;
            Int x = intersection_x(a_it, b_it, a, b);
            if (x <= l_it) {
                segs.erase(pit);
                ends.erase(pit_x);
            } else {
                l = x;
                if (x < r_it) {
                    r_it = x;
                    ends.erase(pit_x);
                    ends.emplace_hint(it_x, r_it, Line{a_it, b_it});
                }
                break;
            }
        }
        if (l < r) {
            segs.emplace_hint(it, a, Segment{b, l, r});
            ends.emplace_hint(it_x, r, Line{a, b});
        }
    }

    Long get_max(Int x) {
        assert(IntMin <= x && x < IntMax);
        assert(!segs.empty());
        auto [a, b] = ends.upper_bound(x)->second;
        return (Long)a * x + b;
    }
};

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  VI a(n);
  rep(i, n) cin >> a[i];
  CHT<ll, ll> d1, d2;
  d1.add_line(0, 0);
  ll v_last = 0;
  rep(i, n) {
    ll v = d1.get_max(a[i]);
    d2.add_line(a[i], v);
    v_last = max(v_last - a[i], d2.get_max(i + 1));
    if (i == n - 1) cout << v_last << '\n';
    d1.add_line(-(i + 1), v_last);
  }
}
0