Submission #1182245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182245		AlgorithmWarrior	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	9 ms	2488 KiB

semiexpress

#include <bits/stdc++.h>

using namespace std;

int const MAX=3005;
int n,m,k;
int a,b,c;
long long timp;
int stops[MAX];
vector<int>add;

void read(){
    cin>>n>>m>>k>>a>>b>>c>>timp;
    int i;
    for(i=1;i<=m;++i)
        cin>>stops[i];
}

int solve(){
    int ans=-1;
    int i;
    for(i=1;i<m;++i){
        long long total=1LL*(stops[i]-1)*b;
        if(total<=timp){
            long long ramas=timp-total;
            int id=min(stops[i]+ramas/a+1,(long long)stops[i+1]);
            ans+=id-stops[i];
            int limit=0;
            while(id<stops[i+1] && limit<k-m){
                int last_id=id;
                long long ramas=timp-total-1LL*(id-stops[i])*c;
                if(ramas<0)
                    break;
                id=min(id+ramas/a+1,(long long)stops[i+1]);
                add.push_back(id-last_id);
                ++limit;
            }
        }
    }
    if(1LL*(n-1)*b<=timp)
        ++ans;
    sort(add.begin(),add.end(),greater<int>());
    for(i=0;i<(int)add.size() && i<k-m;++i)
        ans+=add[i];
    return ans;
}

int main()
{
    read();
    cout<<solve();
    return 0;
}

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