Submission #54198

#	Time	Username	Problem	Language	Result	Execution time	Memory
54198		ksun48	Long Distance Coach (JOI17_coach)	C++14	46 / 100	2070 ms	764 KiB

coach

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;

LL cnt(LL m, LL a, LL b, LL T){
	a -= m;
	b -= m;
	if(b < 0) return 0;
	a = max(a, 0LL);
	b = max(b, 0LL);
	LL f = (a+T-1)/T;
	LL g = (b)/T;
	return max(g-f+1, 0LL);
}

int main(){
	cin.sync_with_stdio(0); cin.tie(0);
	LL X, N, M, W, T;
	cin >> X >> N >> M >> W >> T;
	// X = total duration
	// N = # stops
	// M = # passenges
	vector<LL> stop;
	stop.push_back(0);
	for(LL i = 0; i < N; i++){
		LL s;
		cin >> s;
		stop.push_back(s);
	}
	stop.push_back(X);
	sort(stop.begin(), stop.end());

	// W = cost
	vector<pair<LL,LL> > times;

	LL totalrefundcost = 0;
	for(LL i = 0; i < M; i++){
		LL d, c;
		cin >> d >> c;
		times.push_back({d,c});
		totalrefundcost += c;
	}
	sort(times.begin(), times.end());

	vector<LL> t;
	vector<LL> refundcost;
	t.push_back(0);
	refundcost.push_back(0); // but you must always feed the driver
	for(int i = 0; i < M; i++){
		t.push_back(times[i].first);
		refundcost.push_back(times[i].second);
	}
	t.push_back(T);
	refundcost.push_back(0); // should not use this result
	vector<LL> dp(refundcost.size(), W*(X+1));
	dp[0] = 0;
	for(int j = 1; j < refundcost.size(); j++){
		LL totrefund = 0;
		for(int i = j-1; i >= 0; i--){
			if(i + 1 < j) totrefund += refundcost[i+1];
			LL cost = dp[i] + totrefund;
			cost += W * cnt(t[i], 0, X, T);
			// keep i, j for sure
			// can only throw people off at stations % T in (t[i], t[j])
			int next = i+1;
			for(int r = 0; r < stop.size() - 1; r++){
				LL R = stop[r+1];
				if(t[i] < (R % T) && (R % T) < t[j]){
					while(t[next] < (R%T)){
						// can kick off
						cost += W * (cnt(t[next], 0, R, T) - 1);
						next++;
					}
				}
			}
			while(next < j){
				cost += W * cnt(t[next], 0, X, T);
				next++;
			}
			dp[j] = min(dp[j], cost);
		}
	}
	// T = time delay
	cout << dp[refundcost.size()-1] << '\n';
}

Compilation message (stderr)

coach.cpp: In function 'int main()':
coach.cpp:57:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j = 1; j < refundcost.size(); j++){
                 ~~^~~~~~~~~~~~~~~~~~~
coach.cpp:66:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int r = 0; r < stop.size() - 1; r++){
                   ~~^~~~~~~~~~~~~~~~~

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