test/aoj2580_0.test.cpp

Back to top page

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

Depends on

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

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2580"
#include "../memo/macro.hpp"
#include "../DP/convex_hull_trick.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 cht;
        REP(j, n) {
            cht.insert(num[j], dp[i-1][j]-num[j]*p[j]);
            dp[i][j] = cht.query(p[j]);
        }
    }

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

    return 0;
}

#line 1 "test/aoj2580_0.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/convex_hull_trick.cpp"
// BEGIN CUT
// 最小を求めてるので最大ならinsert(-a,-b), -get(x)
struct ConvexHullTrick {
    deque<PII> que;

    bool isright(const PII &p1, const PII &p2, int x) {
        return (p1.second-p2.second) >= x * (p2.first-p1.first);
    }
    bool check(const PII &a, const PII &b, const PII &c) {
        return (b.first-a.first)*(c.second-b.second)>=(b.second-a.second)*(c.first-b.first);
    }
    ll f(const PII &p, ll x) { return p.first * x + p.second; }

    // ax+bを追加 (aについて降順にすること)
    void insert(ll a, ll b) {
        PII p(a, b);
        while(que.size() >= 2 && check(que[que.size()-2], que.back(), p)) {
            que.pop_back();
        }
        que.push_back(p);
    }
    // 単調性がある xの位置での最小のy
    ll incl_query(ll x) {
        assert(que.size());
        while(que.size() >= 2 && f(que[0],x) >= f(que[1],x)) {
            que.pop_front();
        }
        return que[0].first * x + que[0].second;
    }
    // 単調性なし
    ll query(ll x) {
        ll lb = -1, ub = (ll)que.size()-1;
        while(ub-lb > 1) {
            ll mid = (lb+ub)/2;
            if(isright(que[mid], que[mid+1], x)) lb = mid;
            else ub = mid;
        }
        return f(que[ub], x);
    }
};
// END CUT
#line 4 "test/aoj2580_0.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 cht;
        REP(j, n) {
            cht.insert(num[j], dp[i-1][j]-num[j]*p[j]);
            dp[i][j] = cht.query(p[j]);
        }
    }

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

    return 0;
}

Back to top page