Submission #1051975

#TimeUsernameProblemLanguageResultExecution timeMemory
1051975alex_2008Semiexpress (JOI17_semiexpress)C++14
18 / 100
0 ms440 KiB
#include <iostream> #include <vector> #include <algorithm> #include <stack> #include <set> #include <queue> using namespace std; typedef long long ll; const int N = 3e3 + 10; ll s[N]; ll n, m, k; ll a, b, c; ll t; ll prev(ll x) { int i = upper_bound(s + 1, s + m + 1, x) - s; return s[i - 1]; } ll nx(ll x) { int i = upper_bound(s + 1, s + m + 1, x) - s; return s[i]; } int main() { cin >> n >> m >> k >> a >> b >> c >> t; for (int i = 1; i <= m; i++) { cin >> s[i]; } ll ans = 0; if ((n - 1) * b <= t) ans++; priority_queue <pair<ll, ll>> Q; for (int i = 1; i < m; i++) { if ((s[i] - 1) * b > t) continue; if ((s[i] - 1) * b + (s[i + 1] - s[i] - 1) * a <= t) { ans += (s[i + 1] - s[i]); continue; } ll mnac = t - (s[i] - 1) * b; ans += (mnac / a) + 1; ll pos = s[i] + (mnac / a) + 1; mnac -= (pos - s[i]) * c; if (mnac >= 0) { ll u = min(s[i + 1] - pos, (mnac / a) + 1); Q.push({ u, pos }); } } int i = k - m; while (i-- && !Q.empty()) { pair <ll, ll> v = Q.top(); Q.pop(); //cout << "? " << v.first << " " << v.second << "\n"; ans += v.first; if (v.second == -1) continue; ll prv = prev(v.second); ll nxt = nx(v.second); ll u = (v.second - prv) * c + (prv - 1) * b; ll mnac = t - u; ll pos = v.second + (mnac / a) + 1; mnac -= (pos - v.second) * c; if (mnac >= 0) { ll z = min(nxt - pos, (mnac / a) + 1); if (pos >= nxt) pos = -1; Q.push({ z, pos }); } } cout << ans - 1 << "\n"; } /* 300 8 16 34 12 23 1234 1 10 77 82 137 210 297 300 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...