Submission #539793

#	Time	Username	Problem	Language	Result	Execution time	Memory
539793		cheissmart	Long Distance Coach (JOI17_coach)	C++14	100 / 100	205 ms	16956 KiB

coach

#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;
const ll oo = ll(1e18) + 7;

struct line {
	ll m, b;
	line(ll _m, ll _b) : m(_m), b(_b) {}
	ll operator () (ll x) { return m * x + b; }
	ll die(line l) {
		assert(m > l.m);
		return (l.b - b) / (m - l.m) + 1;
	}
};
deque<line> dk;

bool last_is_uesless(line l) {
	if(SZ(dk) < 2) return false;
	return dk[SZ(dk) - 2].die(dk.back()) >= dk.back().die(l);
}

void add(line l) {
	while(last_is_uesless(l)) dk.pop_back();
	dk.PB(l);
}

ll qry(ll x) {
	assert(SZ(dk));
	int lb = 0, rb = SZ(dk) - 2;
	while(lb <= rb) {
		int mb = (lb + rb) / 2;
		if(dk[mb](x) < dk[mb + 1](x))
			rb = mb - 1;
		else
			lb = mb + 1;
	}
	return dk[lb](x);
}

signed main()
{
	IO_OP;

	ll x, t;
	int n, m, w;
	cin >> x >> n >> m >> w >> t;
	V<ll> s(n);
	for(int i = 0; i < n; i++)
		cin >> s[i];
	V<pair<ll, int>> a;
	for(int i = 0; i < m; i++) {
		ll d; int c;
		cin >> d >> c;
		a.EB(d, c);
	}
	sort(ALL(a));
	V<ll> aux(m, oo);
	s.PB(x);
	for(ll ss:s) {
		ll sa = ss / t, na = ss % t;
		int pos = int(upper_bound(ALL(a), MP(na, INF)) - a.begin());
		if(pos > 0)
			aux[pos - 1] = min(aux[pos - 1], sa * w);
	}
	V<ll> p(m + 1);
	for(int i = 0; i < m; i++)
		p[i + 1] = p[i] + a[i].S;
	V<ll> dp(m + 1);
	for(int i = 0; i <= m; i++) {
		if(i == 0) {
			dp[i] = 1LL * (x / t + 1) * w;
		} else {
			dp[i] = dp[i - 1] + 1LL * (x / t + 1 - (a[i - 1].F % t > x % t)) * w;
			if(aux[i - 1] != oo)
				dp[i] = min(dp[i], qry(aux[i - 1]) + i * aux[i - 1] + p[i]);
		}	
		ll m = -i, b = dp[i] - p[i];
		add(line(m, b));
	}
	cout << dp.back() << '\n';
}

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