compro-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ningenMe/compro-library

:heavy_check_mark: test/convex-hull-trick/ConvexHullTrickMonotone-max.test.cpp

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/409"

#include <iostream>
#include <vector>
#include <queue>
#include <cassert>
using namespace std;
#include "../../lib/99-operator/operator/ValueMax.cpp"
#include "../../lib/16-convex-hull-trick/ConvexHullTrickMonotone.cpp"
using ll = long long;

int main(void){
	ll N,A,B,W; cin >> N >> A >> B >> W;
	vector<ll> D(N+2,0);
	for(int i = 1; i <= N; ++i) cin >> D[i];
	// dp[i]=min{j:[0,i)} -> dp[j]+B*k*(k+1)/2-k*A+D[i] (k=i-j-1)
	//                    -> dp[j]+B*(i-j-1)*(i-j)/2-(i-j-1)*A+D[i]
	//                    -> dp[j]+B/2*(i*i-2*i*j+j*j-i+j)-A*(i-j-1)+D[i]
	//                    -> (-B*j)*i  +  dp[j]+B/2*(j*j+j)+A*j  +  B/2*(i*i-i)-A*(i-1)+D[i] 
	// dp[i]=-max{j:[0,i)}-> (B*j)*i  +  -{dp[j]+B/2*(j*j+j)+A*j} 
	//                    ->
	vector<ll> dp(N+2,1e15);
	dp[0]=W;
	ConvexHullTrickMonotone<ValueMax<ll>> cht;
	cht.insert(0,-dp[0]);
	for(ll i=1;i<=N+1;++i){
		dp[i]=-cht.get(i) + B*(i*i-i)/2-A*(i-1)+D[i];
		cht.insert(B*i,-(dp[i]+B*(i*i+i)/2+A*i));
	}
	cout << dp[N+1] << endl;
	return 0;
}
#line 1 "test/convex-hull-trick/ConvexHullTrickMonotone-max.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/409"

#include <iostream>
#include <vector>
#include <queue>
#include <cassert>
using namespace std;
#line 1 "lib/99-operator/operator/ValueMax.cpp"
//最大値クエリ
template<class T> struct ValueMax {
	using TypeValue = T;
	inline static constexpr TypeValue unit_value = -3e18;
	inline static constexpr bool func_compare(TypeValue l,TypeValue r){return l>r;}
};
#line 1 "lib/16-convex-hull-trick/ConvexHullTrickMonotone.cpp"
/*
 * @title ConvexHullTrickMonotone - 単調CHT
 * @docs md/convex-hull-trick/ConvexHullTrickMonotone.md
 */
template<class Operator> class ConvexHullTrickMonotone {
private:
    using TypeValue = typename Operator::TypeValue;

    //front->backに向かって傾きがa1<a2<...<aN
    deque<pair<TypeValue,TypeValue>> lines;

    //3直線に関してline2が必要か確認 (このとき a1 < a2 < a3が必要=dequeの順そのまま)
    inline int is_required(const pair<TypeValue,TypeValue>& line1, const pair<TypeValue,TypeValue>& line2, const pair<TypeValue,TypeValue>& line3) {
        return Operator::func_compare((line2.second-line3.second)*(line2.first-line1.first),(line1.second-line2.second)*(line3.first-line2.first));
    }

    //y=ax+bの値
    inline TypeValue y(const pair<TypeValue,TypeValue> line, TypeValue x) {
        return line.first * x + line.second;
    }

    inline void insert_back(const pair<TypeValue,TypeValue> line){
        //傾きが同じとき
        if(lines.size() && lines.back().first == line.first){
            if(Operator::func_compare(lines.back().second,line.second)) return;
            else lines.pop_back();
        }
        //不必要な直線を取り除く
        while (lines.size() > 1 && !is_required(lines[(int)lines.size()-2], lines[(int)lines.size()-1],line)) lines.pop_back();
        //backにinsert
        lines.push_back(line);
    }
    inline void insert_front(const pair<TypeValue,TypeValue> line){
        //傾きが同じとき
        if(lines.size() && lines.front().first == line.first){
            if(Operator::func_compare(lines.front().second,line.second)) return;
            else lines.pop_front();
        }
        //不必要な直線を取り除く
        while (lines.size() > 1 && !is_required(line, lines[0], lines[1])) lines.pop_front();
        //frontにinsert
        lines.push_front(line);
    }
public:
    ConvexHullTrickMonotone() {
        // do nothing
    }
    inline void insert(const TypeValue a, const TypeValue b) {
        insert({a,b});
    }
    //傾きの大きさが常に最大or最小になるようにinsertする
    inline void insert(const pair<TypeValue,TypeValue> line) {
        if(lines.empty() || line.first <= lines.front().first) insert_front(line);
        else if(lines.back().first <= line.first) insert_back(line);
        else assert(false);
    }
    //O(log(N))
    inline TypeValue get(TypeValue x) {
        if(lines.empty()) return Operator::unit_value;
        int ng = -1, ok = (int)lines.size()-1, md;
        while (ok - ng > 1) {
            md = (ok + ng) >> 1;
            ( Operator::func_compare(y(lines[md],x),y(lines[md+1],x)) ?ok:ng)=md;
        }
        return y(lines[ok],x);
    }
    //O(log(N))
    inline pair<TypeValue,TypeValue> get_line(TypeValue x) {
        if(lines.empty()) return {0,Operator::unit_value};
        int ng = -1, ok = (int)lines.size()-1, md;
        while (ok - ng > 1) {
            md = (ok + ng) >> 1;
            ( Operator::func_compare(y(lines[md],x),y(lines[md+1],x)) ?ok:ng)=md;
        }
        return lines[ok];
    }
    //O(N)
    inline void clear(void) {
        lines.clear();
    }
};
#line 10 "test/convex-hull-trick/ConvexHullTrickMonotone-max.test.cpp"
using ll = long long;

int main(void){
	ll N,A,B,W; cin >> N >> A >> B >> W;
	vector<ll> D(N+2,0);
	for(int i = 1; i <= N; ++i) cin >> D[i];
	// dp[i]=min{j:[0,i)} -> dp[j]+B*k*(k+1)/2-k*A+D[i] (k=i-j-1)
	//                    -> dp[j]+B*(i-j-1)*(i-j)/2-(i-j-1)*A+D[i]
	//                    -> dp[j]+B/2*(i*i-2*i*j+j*j-i+j)-A*(i-j-1)+D[i]
	//                    -> (-B*j)*i  +  dp[j]+B/2*(j*j+j)+A*j  +  B/2*(i*i-i)-A*(i-1)+D[i] 
	// dp[i]=-max{j:[0,i)}-> (B*j)*i  +  -{dp[j]+B/2*(j*j+j)+A*j} 
	//                    ->
	vector<ll> dp(N+2,1e15);
	dp[0]=W;
	ConvexHullTrickMonotone<ValueMax<ll>> cht;
	cht.insert(0,-dp[0]);
	for(ll i=1;i<=N+1;++i){
		dp[i]=-cht.get(i) + B*(i*i-i)/2-A*(i-1)+D[i];
		cht.insert(B*i,-(dp[i]+B*(i*i+i)/2+A*i));
	}
	cout << dp[N+1] << endl;
	return 0;
}
Back to top page