Submission #1308090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308090		wangzhiyi33	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	2 ms	584 KiB

semiexpress

#include<bits/stdc++.h>
using namespace std;
#define int long long 

int n,m,k,a,b,c,ti;
int pos[3002];

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>k>>a>>b>>c>>ti;
    for(int q=1;q<=m;q++){
        cin>>pos[q];
    }

    int ans=0;

    priority_queue<array<int,3> >pq;
    // tmbh, akh, grup 

    for(int q=1;q<m;q++) {
        int hrs=(pos[q]-1)*b;
        if(hrs>ti)break;

        int nxt=(ti-hrs)/a;
        nxt=min(nxt,pos[q+1]-pos[q]-1);
        nxt=pos[q]+nxt;
        ans+=(nxt-pos[q]+1);
        
        if(nxt+1<pos[q+1]){
            int sisa=ti-(pos[q]-1)*b-(nxt+1-pos[q])*c;
            if(sisa<0)continue;
            int brp=sisa/a;
            brp=min(brp,pos[q+1]-nxt-2);
            pq.push({brp+1,nxt+brp+1,q});
        }
        
    }

    k-=m;
    while(k && pq.size()){
        array<int,3>apa=pq.top();
        pq.pop();
        k--;
      //  cout<<apa[0]<<" "<<apa[1]<<" "<<apa[2]<<endl;
        ans+=apa[0];

        if(apa[1]+1>=pos[apa[2]+1])continue;
        int sisa=ti-(pos[apa[2]]-1)*b-(apa[1]+1-pos[apa[2]])*c;
        if(sisa<0)continue;

        int brp=sisa/a;
        brp=min(brp,pos[apa[2]+1]-apa[1]-2);
        pq.push({brp+1,apa[1]+brp+1,apa[2]});
     //   k--;
    }

    ans--;
    if((n-1)*b<=ti){
        ans++;
    }
    cout<<ans<<endl;
}

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