Submission #53886

#	Time	Username	Problem	Language	Result	Execution time	Memory
53886		ksun48	Long Distance Coach (JOI17_coach)	C++14	16 / 100	7 ms	880 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;
	for(int i = 0; i < M; i++){
		t.push_back(times[i].first);
		refundcost.push_back(times[i].second);
	}
	// T = time delay
	LL bestcost = W*(X+1);
	for(LL z = 0; z < (1<<M); z++){
		LL currentcost = 0;
		for(int a = 0; a < M; a++){
			if((1<<a) & z){
				currentcost += refundcost[a];
			}
		}
		vector<LL> onbus(M, 1);
		for(int i = 0; i < stop.size()-1; i++){
			// stops[i] to stop[i+1]
			LL lastdriver = (stop[i+1] / T) * T;
			if(stop[i] <= lastdriver){
				currentcost += W * cnt(0, stop[i], lastdriver, T);
				for(int j = 0; j < M; j++){
					if(onbus[j]){
						currentcost += W * cnt(t[j], stop[i], lastdriver, T);
					}
				}
			}
			vector<LL> drinkers;
			for(int j = 0; j < M; j++){
				if(onbus[j]){
					LL tdrink = lastdriver + t[j];
					if(stop[i] <= tdrink && tdrink <= stop[i+1]){
						drinkers.push_back(j);
					}
				}
			}
			reverse(drinkers.begin(), drinkers.end());
			currentcost += W * (LL)drinkers.size();
			for(LL a : drinkers){
				if((1<<a) & z){
					currentcost -= W;
					onbus[a] = 0;
				} else {
					 break;
				}
			}
		}
		bestcost = min(bestcost, currentcost);
	}
	cout << bestcost << '\n';
}

Compilation message (stderr)

coach.cpp: In function 'int main()':
coach.cpp:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < stop.size()-1; i++){
                  ~~^~~~~~~~~~~~~~~

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