Submission #821471

#	Time	Username	Problem	Language	Result	Execution time	Memory
821471		AdamGS	Long Distance Coach (JOI17_coach)	C++17	71 / 100	2058 ms	12932 KiB

coach

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(ll a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=2e5+7;
ll T[LIM], dp[LIM], kiedy[LIM], x, n, m, w, t;
pair<ll,ll>P[LIM];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> x >> n >> m >> w >> t;
	rep(i, n) cin >> T[i];
	T[n]=x; ++n;
	rep(i, m) cin >> P[i].st >> P[i].nd;
	sort(T, T+n);
	sort(P, P+m);
	rep(i, m) kiedy[i]=INF;
	rep(i, n) {
		ll po=0, ko=m-1;
		while(po<ko) {
			ll sr=(po+ko+1)/2;
			if(P[sr].st>T[i]%t) ko=sr-1; else po=sr;
		}
		if(P[po].st>T[i]%t) continue;
		kiedy[po]=min(kiedy[po], T[i]/t);
	}
	rep(i, m+1) {
		ll ile=w*(x/t);
		if(x%t>P[i].st) ile+=w;
		dp[i]=ile;
		if(i) dp[i]+=dp[i-1];
		if(kiedy[i]==INF) continue;
		ll sumc=0;
		for(ll j=i-1; j>=0; --j) {
			sumc+=P[j+1].nd;
			dp[i]=min(dp[i], dp[j]+sumc+(i-j)*kiedy[i]*w);
		}
		sumc+=P[0].nd;
		dp[i]=min(dp[i], sumc+(i+1)*kiedy[i]*w);
	}
	cout << dp[m-1]+w*(x/t+1) << '\n';
}

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