Submission #669124

#	Time	Username	Problem	Language	Result	Execution time	Memory
669124		Dec0Dedd	Semiexpress (JOI17_semiexpress)	C++14	0 / 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;
ll 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 (s[i]+x >= s[i+1]) x=s[i+1]-s[i]-1;
        ans+=x+1;
        ll nxt=s[i]+x+1;
        
        ll sz=s[i+1]-nxt, cost=tmp+(nxt-s[i])*c, h=(t-cost)/a;

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

    while (k--) {
        pp x=pq.top(); pq.pop();
        int i=x.second.first, nxt=x.second.second;
        ans+=x.first; nxt+=x.first;

        ll sz=s[i+1]-nxt, cost=b*(s[i]-1)+(nxt-s[i])*c, h=(t-cost)/a;
        if (min(sz, h) <= 0) continue;
        else pq.push({min(sz, h), {i, nxt}});
    }

    if (c <= t) ++ans;
    cout<<ans<<"\n";
}

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