Submission #991503

#TimeUsernameProblemLanguageResultExecution timeMemory
991503horezusholSemiexpress (JOI17_semiexpress)C++14
0 / 100
1049 ms344 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...