Submission #1086334

#TimeUsernameProblemLanguageResultExecution timeMemory
1086334_callmelucianSemiexpress (JOI17_semiexpress)C++14
100 / 100
1 ms464 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> pl; typedef pair<int,int> pii; typedef tuple<int,int,int> tt; #define all(a) a.begin(), a.end() #define filter(a) a.erase(unique(all(a)), a.end()) ll curExtend[3003], s[3003]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m, k; cin >> n >> m >> k; ll A, B, C; cin >> A >> C >> B; ll T; cin >> T; for (int i = 1; i <= m; i++) { cin >> s[i]; s[i]--; } s[m + 1] = n; priority_queue<pl> pq; function<ll(int)> refine = [&] (int i) { if (C * s[i] + B * (curExtend[i] + 1) > T) return 0LL; ll extend = (T - C * s[i] - B * (curExtend[i] + 1)) / A + 1; return min(extend, s[i + 1] - (s[i] + curExtend[i]) - 1); }; ll ans = 0; for (int i = 1; i <= m; i++) { curExtend[i] = -1, curExtend[i] += refine(i); ans += curExtend[i] + (i > 1); pq.emplace(refine(i), i); } for (int i = 0; i < k - m && pq.size(); i++) { ll incr, place; tie(incr, place) = pq.top(); pq.pop(); curExtend[place] += incr, ans += incr; pq.emplace(refine(place), place); } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...