#include<bits/stdc++.h>
const char nl = '\n';
using namespace std;
using ll = long long;
const ll N = 2e5;
ll n, m, k;
ll a, b, c;
ll t;
ll s[N];
ll p[N];
map<ll, ll> S, P;
ll dp[N]; // minimum time to get to the i-th station
void solve() {
cin >> n >> m >> k;
cin >> a >> b >> c;
cin >> t;
for (ll i = 1; i <= m; i ++) {
cin >> s[i];
p[i] = s[i];
S[s[i]] = i;
P[p[i]] = i;
}
for (ll i = 1; i <= n; i ++) { // only with train
dp[i] = (i - 1)*a;
}
for (ll i = 1; i <= m; i ++) { // only with express
dp[s[i]] = min(dp[s[i]], (s[i] - 1)*b);
}
for (ll i = 1; i <= m; i ++) { // only with semi
dp[p[i]] = min(dp[p[i]], (p[i] - 1)*c);
}
for (ll i = 2; i <= n; i ++) { // train + express + semi
dp[i] = min(dp[i], dp[i-1] + a);
if (S[i]) {
dp[i] = min(dp[i], dp[s[S[i]-1]] + (i - s[S[i]-1])*b);
}
if (P[i]) {
dp[i] = min(dp[i], dp[p[P[i]-1]] + (i - p[P[i]-1])*c);
}
// s[S[i]-1] position of station before that one
}
vector<ll> sick;
ll res = 0;
for (ll i = 2; i <= n; i ++) {
if (dp[i] > t && !P[i]) {
sick.push_back(i);
} else {
res ++;
}
}
// ~debug
// for (ll i = 1; i <= n; i ++) {
// cout << dp[i] << " ";
// }
// cout << nl;
// for (auto i : sick) {
// cout << i << " ";
// }
// cout << nl;
// ~
for (ll fi = 0; fi < (ll)sick.size(); fi ++) {
for (ll se = fi+1; se < (ll)sick.size(); se ++) {
vector<ll> cur = {0};
vector<ll> dp2 = {0};
for (ll i = 1; i <= m; i ++) {
cur.push_back(p[i]);
}
for (ll i = 1; i <= n; i ++) {
dp2.push_back(dp[i]);
}
cur.push_back(sick[fi]);
cur.push_back(sick[se]);
sort(cur.begin(), cur.end());
map<ll, ll> mp;
for (ll i = 1; i <= m+2; i ++) {
mp[cur[i]] = i;
}
for (ll i = 2; i <= n; i ++) {
dp2[i] = min(dp2[i], dp2[i-1] + a);
if (S[i]) {
dp2[i] = min(dp2[i], dp2[s[S[i]-1]] + (i - s[S[i]-1])*b);
}
if (mp[i]) {
dp2[i] = min(dp2[i], dp2[cur[mp[i]-1]] + (i - cur[mp[i]-1])*c);
}
}
ll ans = 0;
for (ll i = 2; i <= n; i ++) {
if (dp2[i] <= t) {
ans ++;
}
}
res = max(res, ans);
// ~debug
// cout << "\n------------\n";
// for (ll i = 1; i <= m+2; i ++) {
// cout << cur[i] << " ";
// }
// cout << nl;
// for (ll i = 1; i <= n; i ++) {
// cout << dp2[i] << " ";
// }
// cout << "\n------------\n";
// ~
}
}
cout << res;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll tst = 1;
// cin >> tst;
while (tst --) {
solve();
cout << nl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Incorrect |
283 ms |
4444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Incorrect |
283 ms |
4444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Incorrect |
283 ms |
4444 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
