제출 #1182245

#제출 시각아이디문제언어결과실행 시간메모리
1182245AlgorithmWarriorSemiexpress (JOI17_semiexpress)C++20
100 / 100
9 ms2488 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...