Submission #1347552

#TimeUsernameProblemLanguageResultExecution timeMemory
1347552WarinchaiSemiexpress (JOI17_semiexpress)C++20
100 / 100
1 ms344 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;

vector<int>v;

struct node{
    int st,en,cur,can;
    node(int _st=0,int _en=0,int _cur=0,int _can=0){
        st=_st,en=_en,cur=_cur,can=_can;
    }
    friend bool operator<(node a,node b){
        return a.can<b.can;
    }
};

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m,k;cin>>n>>m>>k;
    int a,b,c;cin>>a>>b>>c;
    int t;cin>>t;
    for(int i=0;i<m;i++){
        int x;cin>>x;
        v.push_back(x);
    }
    priority_queue<node>pq;
    int ans=0;
    for(int i=0;i<m;i++){
        if(i==m-1){
            int cost=(v[i]-1)*b;
            int left=t-cost;
            ans+=(left>=0);
            continue;
        }
        node temp=node(v[i],v[i+1],v[i],0);
        int cost=(temp.st-1)*b+(temp.cur-temp.st)*c;
        int left=t-cost;
        if(left<0)continue;
        //cerr<<"left:"<<left<<"\n";
        int can=min(left/a+1,temp.en-temp.cur);
        //cerr<<"can:"<<can<<"\n";
        //
        ans+=can;
        temp.cur+=can;
        if(temp.cur==temp.en)continue;
        cost=(temp.st-1)*b+(temp.cur-temp.st)*c;
        left=t-cost;
        if(left<0)continue;
        //cerr<<"left:"<<left<<"\n";
        can=min(left/a+1,temp.en-temp.cur);
        temp.can=can;
        //cerr<<"can:"<<can<<"\n";
        pq.push(temp);
        //cerr<<temp.st<<" "<<temp.en<<" "<<temp.can<<" "<<temp.cur<<"\n";
    }
    //cerr<<"ans:"<<ans<<"\n";
    int cnt=m;
    while(!pq.empty()){
        cnt++;
        if(cnt>k)break;
        //cerr<<cnt<<"\n";
        auto temp=pq.top();
        pq.pop();
        ans+=temp.can;
        temp.cur+=temp.can;
        if(temp.cur==temp.en)continue;
        int cost=(temp.st-1)*b+(temp.cur-temp.st)*c;
        int left=t-cost;
        if(left<0)continue;
        //cerr<<"left:"<<left<<"\n";
        int can=min(left/a+1,temp.en-temp.cur);
        temp.can=can;
        //cerr<<"can:"<<can<<"\n";
        pq.push(temp);
        //cerr<<temp.st<<" "<<temp.en<<" "<<temp.can<<" "<<temp.cur<<"\n";
    }
    cout<<ans-1;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...