Submission #1187413

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

semiexpress

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

const long long MX=3e5+10;
long long s[MX],vc[MX];

long long n,m,k,a,b,c,t;

long long fget(long long i)
{
    long long o=t-(s[i]-1)*b-c*(vc[i]-s[i]);
    
    if(o<0)
    {
        return vc[i];
    }
    
    return min(vc[i]+o/a+1,s[i+1]);
}
int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    
    
    cin>>n>>m>>k>>a>>b>>c>>t;
    
    for(long long i=1;i<=m;i++)
    {
        cin>>s[i];
    }
    
    long long ans=((n-1)*b<=t);
    for(long long i=1;i<m;i++)
    {
        if((s[i]-1)*b<=t)
        {
            vc[i]=s[i];
            ans+=fget(i)-vc[i];
            vc[i]=fget(i);
        }
        else
        {
            vc[i]=0;
        }
    }
    
    priority_queue < pair < long long , long long > > q;
    for(long long i=1;i<m;i++)
    {
        if(vc[i])
        {
            q.push({fget(i)-vc[i],i});
        }
    }
    
    for(long long i=0;i<k-m;i++)
    {
        long long in=q.top().second;
        q.pop();
        
        ans+=fget(in)-vc[in];
        vc[in]=fget(in);
        
        q.push({fget(in)-vc[in],in});
    }
    
    cout<<ans-1<<"\n";
    return 0;
}

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