Submission #1179921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179921		user736482	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	0 ms	328 KiB

semiexpress

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define INFL 1000000000000000099LL

ll n,q,s,t,a,b,c,d,ans,k,m,K;
vector<ll>szy;

priority_queue<pair<pair<ll,ll>,pair<ll,ll>>>pq;//ile dodaje, koniec,koniec calosci

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>k>>a>>b>>c>>t;
    K=k;
    for(ll i=0;i<m;i++){
        cin>>d;
        d--;
        szy.pb(d);
        if(i){
            ll kn=(t-szy[i-1]*b)/a + szy[i-1];
            //cout<<kn<<"\n\n";
            if(t-szy[i-1]*b<0)k--;
            else if(kn>=szy[i]){
                k--;
                ans+=szy[i]-szy[i-1];
            }
            else{
                k--;
               // cout<<"xd";
                ans+=kn-szy[i-1]+1;
                ll pom=(t-szy[i-1]*b-(kn-szy[i-1]+1)*c)/a + 1;
             //   cout<<szy[i]-kn<<" "<<min(pom,szy[i]-kn)<<"\n\n";
             if((t-szy[i-1]*b-(kn-szy[i-1]+1)*c)>=0)
                pq.push({{min(pom,szy[i]-kn-1),min(kn+pom,szy[i]-1)},{szy[i],szy[i-1]}});
            }

        }
    }
  //  cout<<ans;
    k--;
    while(pq.size() && k){
        k--;
        auto pom=pq.top();
        pq.pop();
        
        ans+=pom.ff.ff;
     //   cout<<pom.ff.ff<<" "<<pom.ff.ss<<" "<<pom.ss.ff<<" "<<pom.ss.ss<<"\n";
        if(pom.ff.ss==pom.ss.ff)continue;
        ll kn=pom.ff.ss;
        ll pomm=(t-pom.ss.ss*b-(kn-pom.ss.ss+1)*c)/a + 1;
        if((t-pom.ss.ss*b-(kn-pom.ss.ss+1)*c)>=0)
        pq.push({{min(pomm,pom.ss.ff-kn-1),min(kn+pomm,pom.ss.ff-1)},pom.ss});
    }
   /// cout<<ans;
    if((n-1)*b>t)ans--;
    cout<<ans;
    
    
}

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