#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
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++){
~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Correct |
2 ms |
412 KB |
Output is correct |
| 4 |
Correct |
2 ms |
416 KB |
Output is correct |
| 5 |
Correct |
3 ms |
468 KB |
Output is correct |
| 6 |
Correct |
3 ms |
516 KB |
Output is correct |
| 7 |
Correct |
3 ms |
628 KB |
Output is correct |
| 8 |
Correct |
5 ms |
632 KB |
Output is correct |
| 9 |
Correct |
3 ms |
636 KB |
Output is correct |
| 10 |
Correct |
3 ms |
640 KB |
Output is correct |
| 11 |
Correct |
2 ms |
756 KB |
Output is correct |
| 12 |
Correct |
4 ms |
756 KB |
Output is correct |
| 13 |
Correct |
3 ms |
780 KB |
Output is correct |
| 14 |
Correct |
4 ms |
780 KB |
Output is correct |
| 15 |
Correct |
3 ms |
780 KB |
Output is correct |
| 16 |
Correct |
4 ms |
780 KB |
Output is correct |
| 17 |
Correct |
3 ms |
780 KB |
Output is correct |
| 18 |
Correct |
2 ms |
780 KB |
Output is correct |
| 19 |
Correct |
3 ms |
780 KB |
Output is correct |
| 20 |
Correct |
2 ms |
880 KB |
Output is correct |
| 21 |
Correct |
3 ms |
880 KB |
Output is correct |
| 22 |
Correct |
2 ms |
880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Correct |
2 ms |
412 KB |
Output is correct |
| 4 |
Correct |
2 ms |
416 KB |
Output is correct |
| 5 |
Correct |
3 ms |
468 KB |
Output is correct |
| 6 |
Correct |
3 ms |
516 KB |
Output is correct |
| 7 |
Correct |
3 ms |
628 KB |
Output is correct |
| 8 |
Correct |
5 ms |
632 KB |
Output is correct |
| 9 |
Correct |
3 ms |
636 KB |
Output is correct |
| 10 |
Correct |
3 ms |
640 KB |
Output is correct |
| 11 |
Correct |
2 ms |
756 KB |
Output is correct |
| 12 |
Correct |
4 ms |
756 KB |
Output is correct |
| 13 |
Correct |
3 ms |
780 KB |
Output is correct |
| 14 |
Correct |
4 ms |
780 KB |
Output is correct |
| 15 |
Correct |
3 ms |
780 KB |
Output is correct |
| 16 |
Correct |
4 ms |
780 KB |
Output is correct |
| 17 |
Correct |
3 ms |
780 KB |
Output is correct |
| 18 |
Correct |
2 ms |
780 KB |
Output is correct |
| 19 |
Correct |
3 ms |
780 KB |
Output is correct |
| 20 |
Correct |
2 ms |
880 KB |
Output is correct |
| 21 |
Correct |
3 ms |
880 KB |
Output is correct |
| 22 |
Correct |
2 ms |
880 KB |
Output is correct |
| 23 |
Incorrect |
7 ms |
880 KB |
Output isn't correct |
| 24 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Correct |
2 ms |
412 KB |
Output is correct |
| 4 |
Correct |
2 ms |
416 KB |
Output is correct |
| 5 |
Correct |
3 ms |
468 KB |
Output is correct |
| 6 |
Correct |
3 ms |
516 KB |
Output is correct |
| 7 |
Correct |
3 ms |
628 KB |
Output is correct |
| 8 |
Correct |
5 ms |
632 KB |
Output is correct |
| 9 |
Correct |
3 ms |
636 KB |
Output is correct |
| 10 |
Correct |
3 ms |
640 KB |
Output is correct |
| 11 |
Correct |
2 ms |
756 KB |
Output is correct |
| 12 |
Correct |
4 ms |
756 KB |
Output is correct |
| 13 |
Correct |
3 ms |
780 KB |
Output is correct |
| 14 |
Correct |
4 ms |
780 KB |
Output is correct |
| 15 |
Correct |
3 ms |
780 KB |
Output is correct |
| 16 |
Correct |
4 ms |
780 KB |
Output is correct |
| 17 |
Correct |
3 ms |
780 KB |
Output is correct |
| 18 |
Correct |
2 ms |
780 KB |
Output is correct |
| 19 |
Correct |
3 ms |
780 KB |
Output is correct |
| 20 |
Correct |
2 ms |
880 KB |
Output is correct |
| 21 |
Correct |
3 ms |
880 KB |
Output is correct |
| 22 |
Correct |
2 ms |
880 KB |
Output is correct |
| 23 |
Incorrect |
7 ms |
880 KB |
Output isn't correct |
| 24 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Correct |
2 ms |
412 KB |
Output is correct |
| 4 |
Correct |
2 ms |
416 KB |
Output is correct |
| 5 |
Correct |
3 ms |
468 KB |
Output is correct |
| 6 |
Correct |
3 ms |
516 KB |
Output is correct |
| 7 |
Correct |
3 ms |
628 KB |
Output is correct |
| 8 |
Correct |
5 ms |
632 KB |
Output is correct |
| 9 |
Correct |
3 ms |
636 KB |
Output is correct |
| 10 |
Correct |
3 ms |
640 KB |
Output is correct |
| 11 |
Correct |
2 ms |
756 KB |
Output is correct |
| 12 |
Correct |
4 ms |
756 KB |
Output is correct |
| 13 |
Correct |
3 ms |
780 KB |
Output is correct |
| 14 |
Correct |
4 ms |
780 KB |
Output is correct |
| 15 |
Correct |
3 ms |
780 KB |
Output is correct |
| 16 |
Correct |
4 ms |
780 KB |
Output is correct |
| 17 |
Correct |
3 ms |
780 KB |
Output is correct |
| 18 |
Correct |
2 ms |
780 KB |
Output is correct |
| 19 |
Correct |
3 ms |
780 KB |
Output is correct |
| 20 |
Correct |
2 ms |
880 KB |
Output is correct |
| 21 |
Correct |
3 ms |
880 KB |
Output is correct |
| 22 |
Correct |
2 ms |
880 KB |
Output is correct |
| 23 |
Incorrect |
7 ms |
880 KB |
Output isn't correct |
| 24 |
Halted |
0 ms |
0 KB |
- |
