Submission #1081247

#TimeUsernameProblemLanguageResultExecution timeMemory
1081247MkswllSemiexpress (JOI17_semiexpress)C++17
100 / 100
18 ms15964 KiB
#include <bits/stdc++.h> using namespace std; #define vt vector #define F first #define S second #define pb push_back #define all(v) v.begin(), v.end() typedef long long ll; const int MAXN = 1e5 + 5, MAXM = 3e3 + 5; int n, m, k; ll A, B, C; ll T; ll s[MAXM]; list <int> rec[MAXN]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k; cin >> A >> B >> C; cin >> T; for(int i = 1; i <= m; ++i) { cin >> s[i]; } k -= m; int ans = (n - 1) * B <= T; for(int i = 1; i < m && T > 0; ++i, T -= B * (s[i] - s[i - 1])) { ll t = T; int left = s[i + 1] - s[i]; ll take = min(t / A, (ll) left - 1) + 1; ans += take; left -= take; int last = s[i], mx = s[i] + take - 1; int cnt = k; while(left && t > 0 && mx < s[i + 1] - 1 && cnt) { t -= C * (mx + 1 - last); if(t < 0) break; ll take = min(t / A, (ll) left - 1) + 1; rec[i].pb(take); left -= take; last = mx + 1; mx += take; --cnt; } } priority_queue <pair <int, int> > q; for(int i = 1; i < m; ++i) { if(!rec[i].empty()) { q.push({rec[i].front(), i}); rec[i].pop_front(); } } for(int i = 1; i <= k && !q.empty(); ++i) { ans += q.top().F; int cur = q.top().S; q.pop(); if(!rec[cur].empty()) { q.push({rec[cur].front(), cur}); rec[cur].pop_front(); } } cout << ans - 1 << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...