제출 #1336953

#제출 시각아이디문제언어결과실행 시간메모리
1336953nguyenkhangninh99Semiexpress (JOI17_semiexpress)C++20
100 / 100
1 ms344 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, m, k, a, b, c, t; cin >> n >> m >> k >> a >> b >> c >> t; //a: chậm, b: vừa, c: nhanh

    vector<int> cur(m), nxt(m), s(m + 1);
    for(int i = 1; i <= m; i++) cin >> s[i];
    
    int ans = ((n - 1) * b <= t);

    priority_queue<pair<int, int>> pq;
    for(int i = 1; i <= m - 1; i++){
        int reach = (s[i] - 1) * b;
        if(reach <= t){
            ans++;
            cur[i] = min(s[i + 1] - s[i] - 1, (t - reach) / a);
            ans += cur[i];
            int nt = reach + (cur[i] + 1) * c;
            if(nt <= t) pq.push({min(s[i + 1] - s[i] - 1, cur[i] + 1 + (t - nt) / a) - cur[i], i});
        }
    }
    
    for(int i = 1; i <= k - m && pq.size(); i++){
        auto [mx, id] = pq.top();
        pq.pop();
        ans += mx;
        cur[id] += mx;
        int nt = (s[id] - 1) * b + (cur[id] + 1) * c;
        if(nt <= t) pq.push({min(s[id + 1] - s[id] - 1, cur[id] + 1 + (t - nt) / a) - cur[id], id});
    }
    
    cout << ans - 1;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...