test/aoj2603.test.cpp

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=2603

Depends on

Code

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

int main(void) {
    ll s, n, m;
    cin >> s >> n >> m;
    vector<ll> x(s), t(n), p(n);
    REP(i, s) cin >> x[i];
    REP(i, n) cin >> t[i] >> p[i], p[i]--;

    vector<ll> v(n);
    REP(i, n) v[i] = t[i] - x[p[i]];
    sort(ALL(v));
    vector<ll> rui(n+1);
    REP(i, n) rui[i+1] = rui[i]+v[i];

    vector<ll> dp(n+1, INF);
    dp[0] = 0;
    REP(k, m) {
        auto f = [&](ll i, ll j) {
            return i<j ? INF : dp[j]+(i?v[i-1]:0)*(i-j)-(rui[i]-rui[j]);
        };
        auto ndp = monotone_minima<ll>(n+1, n+1, f); 
        REP(i, n+1) dp[i] = ndp[i].second;
    }
    cout << dp[n] << endl;

    return 0;
}

#line 1 "test/aoj2603.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2603"
#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/monotone_minima.cpp"
// BEGIN CUT
// 各iについてf(i,*)のargminとminをペアで返す
template<typename T, typename Compare = less<T>>
vector<pair<ll,T>> monotone_minima(ll h, ll w, const function<T(ll,ll)> &f, const Compare &comp = Compare()) {
    vector<pair<ll,T>> dp(h);
    function<void(ll,ll,ll,ll)> dfs = [&](ll top, ll bottom, ll left, ll right) {
        if(top > bottom) return;
        ll line = (top + bottom) / 2;
        ll idx = left;
        T mi = f(line, left);
        for(ll i=left+1; i<=right; ++i) {
            T cost = f(line, i);
            if(comp(cost, mi)) {
                mi = cost;
                idx = i;
            }
        }
        dp[line] = make_pair(idx, mi);
        dfs(top, line-1, left, idx);
        dfs(line+1, bottom, idx, right);
    };
    dfs(0, h-1, 0, w-1);
    return dp;
}
// END CUT

// https://atcoder.jp/contests/colopl2018-final/tasks/colopl2018_final_c
namespace colocon2018finalC {
    void solve() {
        int n;
        cin >> n;
        vector<ll> a(n);
        REP(i, n) cin >> a[i];
        function<ll(ll,ll)> f = [&](ll i, ll j) {
            return a[j] + (j-i)*(j-i);
        };
        auto dp = monotone_minima(n, n, f);
        for(auto p: dp) cout << p.second << endl;
    }
}
#line 4 "test/aoj2603.test.cpp"

int main(void) {
    ll s, n, m;
    cin >> s >> n >> m;
    vector<ll> x(s), t(n), p(n);
    REP(i, s) cin >> x[i];
    REP(i, n) cin >> t[i] >> p[i], p[i]--;

    vector<ll> v(n);
    REP(i, n) v[i] = t[i] - x[p[i]];
    sort(ALL(v));
    vector<ll> rui(n+1);
    REP(i, n) rui[i+1] = rui[i]+v[i];

    vector<ll> dp(n+1, INF);
    dp[0] = 0;
    REP(k, m) {
        auto f = [&](ll i, ll j) {
            return i<j ? INF : dp[j]+(i?v[i-1]:0)*(i-j)-(rui[i]-rui[j]);
        };
        auto ndp = monotone_minima<ll>(n+1, n+1, f); 
        REP(i, n+1) dp[i] = ndp[i].second;
    }
    cout << dp[n] << endl;

    return 0;
}