Submission #669154

#	Time	Username	Problem	Language	Result	Execution time	Memory
669154		Dec0Dedd	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	1 ms	340 KiB

semiexpress

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<ll, ll>
#define pp pair<ll, pii>

const int M = 3e3+1;

ll s[M], n, m, k, a, b, c, t;

int main() {
    cin>>n>>m>>k; k-=m;
    cin>>a>>b>>c>>t;
    for (int i=1; i<=m; ++i) cin>>s[i];

    priority_queue<pp> pq;
    ll ans=-1;

    for (int i=1; i<m; ++i) {
        ll tmp=b*(s[i]-1), x=(t-tmp)/a;
        if (b*(s[i]-1) > t) continue;
        if (s[i]+x >= s[i+1]) x=s[i+1]-s[i]-1;
        ans+=x+1;

        ll nxt=s[i]+x+1, sz=s[i+1]-nxt;
        ll cost=b*(s[i]-1)+(nxt-s[i])*c;
        if (cost > t) continue;
        ll h=(t-cost)/a+1;

        if (min(sz, h) <= 0) continue;
        pq.push({min(sz, h), {i, nxt}});
    }

    while (k-- && !pq.empty()) {
        pp g=pq.top(); pq.pop();
        ans+=g.first;
        ll nxt=g.second.second+g.first, i=g.second.first;
        ll cost=b*(s[i]-1)+(nxt-s[i])*c, sz=s[i+1]-nxt;
        if (cost > t) continue;
        ll h=(t-cost)/a+1;

        if (min(sz, h) <= 0) continue;
        pq.push({min(sz, h), {i, nxt}});
    }

    if (b*(s[m]-1) <= t) ++ans;
    cout<<ans<<"\n";
}

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52