Submission #737698

#	Time	Username	Problem	Language	Result	Execution time	Memory
737698		1075508020060209tc	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	2 ms	404 KiB

semiexpress

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;int M;int K;
int B;int C;int A;
int T;
int ar[200005];

signed main(){
cin>>n>>M>>K;
cin>>A>>C>>B;
cin>>T;
for(int i=1;i<=M;i++){
    cin>>ar[i];
}
ar[M+1]=n+1;
int ans=0;
K-=M;

priority_queue<pair<int,pair<int,int>>>pq;

for(int i=1;i<=M;i++){
    if((ar[i]-1)*C>T){continue;}
    int t=T-(ar[i]-1)*C;
    t/=A;
    int pl=ar[i]+t;
    pl=min(pl,ar[i+1]-1);
    ans+=pl-ar[i]+1;
    int opl=pl;
    if(pl!=ar[i+1]-1){
        t=T-(ar[i]-1)*C;
        t-=(pl+1-ar[i])*B;
        if(t<0){continue;}
        int lpl=pl+1;
        t/=A;
        int rpl=min(lpl+t,ar[i+1]-1);
        pq.push({rpl-lpl+1,{i,rpl}});
    }
}

while(pq.size()&&K--){
    int i=pq.top().second.first;
    int pl=pq.top().second.second;
    ans+=pq.top().first;
    pq.pop();
    int t;
    if(pl!=ar[i+1]-1){
        t=T-(ar[i]-1)*C;
        t-=(pl+1-ar[i])*B;
        if(t<0){continue;}
        int lpl=pl+1;
        t/=A;
        int rpl=min(lpl+t,ar[i+1]-1);
        pq.push({rpl-lpl+1,{i,rpl}});
    }



}


cout<<ans-1<<endl;




}

Compilation message (stderr)

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:30:9: warning: unused variable 'opl' [-Wunused-variable]
   30 |     int opl=pl;
      |         ^~~

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