/*
Solution:
Runtime:
*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define sz(x) ((int) x.size())
#define all(x) x.begin(), x.end()
#define debug if (true) cerr
using ll = long long;
int N, M, K;
ll A, B, C, T, ans;
vector<int> S;
vector<ll> timeS;
struct Loc {
int toAdd;
int i, l, r;
ll t;
bool operator<(const Loc& o) const {
if (toAdd != o.toAdd) return toAdd > o.toAdd;
else return i < o.i;
}
};
set<Loc> improve;
/*
l = Location of last non-local train
r = One index before the next express train
t = Time at location l
*/
void calcRange(int i, int l, int r, ll t) {
// cout << "calc " << i << " " << l << " " << r << " " << t << '\n';
// Find number reachable by local
ll reachable = min((T-t) / A, (ll) (r-l));
// cout << "reachable " << reachable << " at " << l << '\n';
ans += reachable;
int newLoc = l + 1 + reachable;
ll newT = t + C * (newLoc-l);
if (reachable < r-l && newT <= T) {
// Could improve with a semiexpress train; by how much?
int numLeft = (r-l) - reachable - 1;
ll newReachable = min((T-newT) / A, (ll) numLeft);
int toAdd = 1 + newReachable;
improve.insert({toAdd, i, newLoc, r, newT});
// cout << "improve " << toAdd << " at " << l << '\n';
}
}
void solve() {
cin >> N >> M >> K;
cin >> A >> B >> C;
cin >> T;
ll currT = 0;
rep(i, 0, M) {
int x; cin >> x; x--;
S.push_back(x);
if (i != 0) currT += B * (S[i]-S[i-1]);
timeS.push_back(currT);
}
ans = -1; // Not counting station 1
rep(i, 0, M) {
if (timeS[i] <= T) ans++; // Can reach express station
else break;
if (i == M-1) break;
calcRange(i, S[i], S[i+1]-1, timeS[i]);
}
// Improve while possible
rep(i, 0, K-M) {
if (improve.empty()) break;
Loc l = *improve.begin();
improve.erase(l);
ans++;
calcRange(l.i, l.l, l.r, l.t);
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
312 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
312 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
312 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
312 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
316 KB |
Output is correct |
9 |
Correct |
1 ms |
312 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
256 KB |
Output is correct |
18 |
Correct |
1 ms |
308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
312 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
312 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
316 KB |
Output is correct |
9 |
Correct |
1 ms |
312 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
256 KB |
Output is correct |
18 |
Correct |
1 ms |
308 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
328 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
452 KB |
Output is correct |
24 |
Correct |
1 ms |
316 KB |
Output is correct |
25 |
Correct |
1 ms |
324 KB |
Output is correct |
26 |
Correct |
1 ms |
356 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
452 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
308 KB |
Output is correct |