제출 #1337818

#제출 시각아이디문제언어결과실행 시간메모리
1337818Born_To_LaughSemiexpress (JOI17_semiexpress)C++17
100 / 100
1 ms344 KiB
// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7;
#define int ll
const int maxn = 3010;
int n, m, k;
int A, B, C, T;
int s[maxn];
int cur[maxn];

void solve(){
    cin >> n >> m >> k;
    cin >> A >> B >> C >> T;
    for(int i=1; i<=m; ++i) cin >> s[i];

    priority_queue<pair<int, int>> pq; 
    //val_i
    ll ans = 0;
    for(int i=1; i<=m; ++i){
        int cost = (s[i] - 1) * B;
        if(cost > T) break;
        if(i == m){
            ans++;break;
        }

        cur[i] = min(s[i + 1] - s[i] - 1, (T - cost) / A);
        ans += cur[i] + 1;

        int nxt = cost + (cur[i] + 1) * C;
        if(cur[i] < s[i + 1] - s[i] - 1 && T >= nxt){
            pq.push({min(s[i + 1] - s[i] - 1, (T - nxt) / A + 1 + cur[i]) - cur[i], i});
            // cout << min(s[i + 1] - s[i] - 1, (T - nxt) / A + 1 + cur[i]) - cur[i] << ' ' << i << ' ' << cur[i] << ">>\n";
        }
    }
    for(; k > m && !pq.empty(); k--){
        int i = pq.top().se;
        int val = pq.top().fi;
        pq.pop();

        ans += val;
        cur[i] += val;

        int cost = (s[i] - 1) * B;
        int nxt = cost + (cur[i] + 1) * C;
        if(cur[i] < s[i + 1] - s[i] - 1 && T >= nxt){
            pq.push({min(s[i + 1] - s[i] - 1, (T - nxt) / A + 1 + cur[i]) - cur[i], i});
        }
        // cout << i << ' ' << cur[i] << "_\n";
    }
    cout << ans - 1 << '\n';
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...