Submission #1349706

#TimeUsernameProblemLanguageResultExecution timeMemory
1349706JuanJLSemiexpress (JOI17_semiexpress)C++20
100 / 100
4 ms424 KiB
#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define mset(a,v) memset(a,v,sizeof(a))
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define forn(i,a,b) for(int i = a; i<b; i++)

using namespace std;
typedef long long ll;

int main(){
    ll n,m,k; cin>>n>>m>>k; k-=m;
    ll a,b,c; cin>>a>>b>>c;
    ll t; cin>>t;

    vector<ll> exp(m); forn(i,0,m) cin>>exp[i];
    sort(ALL(exp));

    vector<ll> next(m);
    vector<pair<ll,ll>> pos(m); 
    forn(i,0,m){
        pos[i]={exp[i],(exp[i]-1)*b};
        next[i]=n+1;
        if(i+1<m) next[i]=exp[i+1];
    }

    ll res = 0;

    forn(i,0,m){
        ll time = pos[i].snd;
        ll dtime = t-time;
        ll posi = pos[i].fst;
        ll uso = min(next[i]-(posi+1),dtime/a)+(time<=t?1:0);

        ll newposi = posi+uso;
        ll newtime = time+uso*c;
        pos[i]={newposi,newtime};
        res+=max((ll)0,uso-(i==0?1:0));
    
    }

    

    forn(kk,0,k){
        ll best = 0;
        ll rnewposi;
        ll rnewtime;
        ll ind = -1;
        forn(i,0,m){
            ll time = pos[i].snd;
            ll dtime = t-time;
            ll posi = pos[i].fst;
            ll uso = min(next[i]-(posi+1),dtime/a)+(time<=t?1:0);

            ll newposi = posi+uso;
            ll newtime = time+uso*c;

            if(uso>best){
                best=uso;
                rnewposi=newposi;
                rnewtime=newtime;
                ind = i;
            }
        }
    
        if(ind!=-1) pos[ind]={rnewposi,rnewtime};
        res+=best;
    }
    cout<<res<<'\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...