Submission #1095821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095821		Zero_OP	Long Distance Coach (JOI17_coach)	C++14	100 / 100	113 ms	18528 KiB

coach

#include "bits/stdc++.h"

using namespace std;

#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T> bool minimize(T& a, const T& b){
    if(a > b) return a = b, true;
    return false;
}

template<typename T> bool maximize(T& a, const T& b){
    if(a < b) return a = b, true;
    return false;
}

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vl = vector<ll>;

const int MAX = 2e5 + 5;
const ll inf = 3e18;

int N, M, W;
ll sumC[MAX], dp[MAX], X, T;

struct refilling_point{
    ll S;
    bool operator < (const refilling_point& other){
        return (S % T) < (other.S % T);
    }

} refilling_points[MAX];

struct passenger{
    ll D, C;
    bool operator < (const passenger& other){
        return D < other.D;
    }

} passengers[MAX];

struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
	    k = -k;
        m = -m;
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	ll query(ll x) {
		if(empty()) return inf;
		auto l = *lower_bound(x);
		return -(l.k * x + l.m);
	}
};

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

//    #define filename "task"
//    if(fopen(filename".inp", "r")){
//        freopen(filename".inp", "r", stdin);
//        freopen(filename".out", "w", stdout);
//    }

    cin >> X >> N >> M >> W >> T;
    for(int i = 1; i <= N; ++i){
        cin >> refilling_points[i].S;
    }

    for(int i = 1; i <= M; ++i){
        cin >> passengers[i].D >> passengers[i].C;
    }

    sort(passengers + 1, passengers + 1 + M);

    ll driver_cost = 1LL * W * ((X / T) + 1);

    for(int i = 1; i <= M; ++i){
        sumC[i] = sumC[i - 1] + passengers[i].C;
    }

    LineContainer trick;
    refilling_points[++N].S = X;
    sort(refilling_points + 1, refilling_points + 1 + N);

    for(int i = M, j = N; i >= 1; --i){
        dp[i] = dp[i + 1] + 1ll * W * ((X - passengers[i].D) / T + 1);
        while(j > 0 && (refilling_points[j].S % T) > passengers[i].D){
            trick.add(-1LL * W * (refilling_points[j].S / T), 1LL * W * (refilling_points[j].S / T) * (i + 1) + sumC[i] + dp[i + 1]);
            --j;
        }

        minimize(dp[i], trick.query(i) - sumC[i - 1]);
    }

    cout << dp[1] + driver_cost << '\n';

    return 0;
}

/*

1000000000000 1 1 1000000 6
999999259244
1 123456789

*/

• Subtask 1: 16 / 16
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 29 / 29