Submission #914331

#	Time	Username	Problem	Language	Result	Execution time	Memory
914331		Trisanu_Das	Long Distance Coach (JOI17_coach)	C++17	71 / 100	5 ms	860 KiB

coach

#include <bits/stdc++.h>
 
using namespace std;
 
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF ((int) 1e9)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 2111
 
typedef long long ll;
 
ll dp[maxn], s[maxn], c[maxn], d[maxn];
pair<ll, ll> p[maxn];
vector<int> v[maxn];
 
 
int main(){
	ll x, n, m, w, t;
	cin >> x >> n >> m >> w >> t;
	for(int i = 1; i <= n; i++) cin >> s[i];
	s[n + 1] = x;
	for(int i = 1; i <= m; i++) cin >> p[i].fi >> p[i].se;
	sort(p + 1, p + 1 + m);
	for(int i = 1; i <= m; i++){
		d[i] = p[i].fi;
		c[i] = p[i].se;
	}
	for(int i = 1; i <= n + 1; i++){
		int pos = lower_bound(d + 1, d + 1 + m, s[i] % t) - d - 1;
		v[pos].pb(i);
	}
	dp[0] = s[n + 1] / t * w + w;
	for(int i = 1; i <= m; i++){
		dp[i] = dp[i - 1] + (s[n + 1] - d[i]) / t * w + w;
		for(int pos : v[i]){
			ll cur = s[pos] / t;
			ll cost = 0;
			for(int j = i; j >= 1; j--){
				cost += c[j];
				dp[i] = min(dp[i], dp[j - 1] + cost + (i - j + 1) * cur * w);
			}	
		}
	}
	cout << dp[m] << '\n';
}

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