#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
const char nl = '\n';
using namespace std;
using ll = long long;
const ll N = 400;
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
}
// // ~debug
// for (ll i = 1; i <= n; i ++) {
// cout << dp[i] << " ";
// }
// cout << nl;
// for (auto i : sick) {
// cout << i << " ";
// }
// cout << nl;
// // ~
ll res = 0;
for (ll fi = 1; fi <= n; fi ++) { // N^3
for (ll se = fi+1; se <= n; 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(fi);
cur.push_back(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";
// cout << ans << nl;
// 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 |
Execution timed out |
1049 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1049 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1049 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
