test/aoj2580_1.test.cpp

Back to top page

• category: test
• View this file on GitHub
  • Last commit date: 2020-03-01 12:39:31+09:00
• see: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2580

Depends on

• DP/li_chao_segment_tree.cpp
• memo/macro.hpp

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2580"
#include "../memo/macro.hpp"
#include "../DP/li_chao_segment_tree.cpp"

ll dp[105][10010];
signed main(void) {
    ll n, m, d, x;
    cin >> n >> m >> d >> x;
    vector<ll> p(n), a(m), b(m);
    REP(i, n) cin >> p[i];
    REP(i, m) cin >> a[i] >> b[i];

    REP(i, d) REP(j, n) dp[i][j] = INF;

    {
        ll num = 0;
        REP(j, m) {
            ll pos;
            if(b[j] >= 0) {
                pos = a[j]-b[j];
            } else {
                pos = a[j]+b[j];
            }
            if(pos >= p[0]) num++;
            a[j] += x;
        }
        REP(i, n) dp[0][i] = num * (p[i] - p[0]);
    }

    FOR(i, 1, d) {
        vector<ll> num(n);
        REP(j, m) {
            ll pos;
            if(b[j] >= 0) {
                pos = a[j]-b[j];
            } else {
                pos = a[j]+b[j];
            }
            ll tmp = upper_bound(ALL(p), pos) - p.begin() - 1;
            if(tmp >= 0) num[tmp]++;
            a[j] += x;
        }
        for(ll j=n-2; j>=0; --j) num[j] += num[j+1];

        ConvexHullTrick<ll> cht(0, 1000010);
        REP(j, n) {
            cht.insert(-num[j], -dp[i-1][j]+num[j]*p[j]);
            dp[i][j] = -cht.get(p[j]);
        }
    }

    ll ret = INF;
    REP(i, d) chmin(ret, dp[i][n-1]);
    cout << ret << endl;

    return 0;
}

#line 1 "test/aoj2580_1.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2580"
#line 1 "memo/macro.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
const ll INF = 1LL<<60;
#line 1 "DP/li_chao_segment_tree.cpp"
// BEGIN CUT
// 単調性なしok 動的CHT 各操作O(logN)
template <typename T, const T id = numeric_limits<T>::min()>
class ConvexHullTrick {
private:
    struct line {
        T a, b;
        line(T a_ = 0, T b_ = 0) : a(a_), b(b_) {}
        // ll でも overflow するのに注意
        T get(T x) { return a * x + b; }
    };
    struct node {
        line l;
        node *lch, *rch;
        node(line l_) : l(l_), lch(nullptr), rch(nullptr) {}
    };

    const T minx, maxx;
    node *root = nullptr;

    // [lb, ub]
    node* update(node *p, ll lb, ll ub, line& l) {
        if (!p) return new node(l);
        if (p->l.get(lb) >= l.get(lb) && p->l.get(ub) >= l.get(ub)) return p;
        if (p->l.get(lb) <= l.get(lb) && p->l.get(ub) <= l.get(ub)) {
          p->l = l;
          return p;
        }
        ll mid = (lb + ub) / 2;
        if (p->l.get(mid) < l.get(mid)) swap(p->l, l);
        if (p->l.get(lb) <= l.get(lb)) p->lch = update(p->lch, lb, mid, l);
        else p->rch = update(p->rch, mid + 1, ub, l);
        return p;
    }
    // [lb, ub]
    T query(node *p, ll lb, ll ub, ll t) const {
        if(!p) return id;
        if(ub == lb) return p->l.get(t);
        ll mid = (lb+ub)/2;
        if(t <= mid) return max(p->l.get(t), query(p->lch, lb, mid, t));
        return max(p->l.get(t), query(p->rch, mid + 1, ub, t));
    }
public:
    // getで呼び出しうるxの範囲を指定
    ConvexHullTrick(const T minx_, const T maxx_) : minx(minx_), maxx(maxx_) {}
    // 直線ax+bを追加 最小がほしければ-ax-bを渡してgetの結果に×(-1)する
    void insert(T a, T b) {
        line l(a, b);
        root = update(root, minx, maxx, l);
    }
    // ax+b のうち最大のものを返す
    T get(T x) const { return query(root, minx, maxx, x); }
};
// END CUT
#line 4 "test/aoj2580_1.test.cpp"

ll dp[105][10010];
signed main(void) {
    ll n, m, d, x;
    cin >> n >> m >> d >> x;
    vector<ll> p(n), a(m), b(m);
    REP(i, n) cin >> p[i];
    REP(i, m) cin >> a[i] >> b[i];

    REP(i, d) REP(j, n) dp[i][j] = INF;

    {
        ll num = 0;
        REP(j, m) {
            ll pos;
            if(b[j] >= 0) {
                pos = a[j]-b[j];
            } else {
                pos = a[j]+b[j];
            }
            if(pos >= p[0]) num++;
            a[j] += x;
        }
        REP(i, n) dp[0][i] = num * (p[i] - p[0]);
    }

    FOR(i, 1, d) {
        vector<ll> num(n);
        REP(j, m) {
            ll pos;
            if(b[j] >= 0) {
                pos = a[j]-b[j];
            } else {
                pos = a[j]+b[j];
            }
            ll tmp = upper_bound(ALL(p), pos) - p.begin() - 1;
            if(tmp >= 0) num[tmp]++;
            a[j] += x;
        }
        for(ll j=n-2; j>=0; --j) num[j] += num[j+1];

        ConvexHullTrick<ll> cht(0, 1000010);
        REP(j, n) {
            cht.insert(-num[j], -dp[i-1][j]+num[j]*p[j]);
            dp[i][j] = -cht.get(p[j]);
        }
    }

    ll ret = INF;
    REP(i, d) chmin(ret, dp[i][n-1]);
    cout << ret << endl;

    return 0;
}

Back to top page