Submission #539730

#	Time	Username	Problem	Language	Result	Execution time	Memory
539730		cheissmart	Long Distance Coach (JOI17_coach)	C++14	71 / 100	2050 ms	15348 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 = 1e18;

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);
	}
	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) for(int j = i - 1; j >= 0; j--) {
				dp[i] = min(dp[i], dp[j] + p[i] - p[j] + (i - j) * aux[i - 1] * w);
			}
		}		
	}
	cout << dp.back() << '\n';
}

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