Submission #670057

#	Time	Username	Problem	Language	Result	Execution time	Memory
670057		Darren0724	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	7 ms	4556 KiB

semiexpress

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(),x.end()
const int INF=1e18;
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int L,n,k;cin>>L>>n>>k;
    k=k-n;
    int a,b,c;cin>>a>>b>>c;
    int t;cin>>t;
    vector<int> v(n+1);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    v[n]=L+1;
    priority_queue<int> pq;
    int ans=0;
    for(int i=0;i<n;i++){
        int t1=t-b*(v[i]-1);
        //cout<<t1<<endl;
        int last=v[i]+(t1/a);
        last=min(last,v[i+1]-1);
        if(t1<0){
            break;
        }
        ans+=(last-v[i]+1);
        //cout<<ans<<endl;
        int rec=last;
        for(int j=1;j<=k;j++){
            int t2=t1-(last+1-v[i])*c;
            if(t2<0){
                break;
            }
            last=last+t2/a+1;
            last=min(v[i+1]-1,last);
            if(last<=rec){
                break;
            }
            pq.push(last-rec);
            rec=last;
        }
    }
    for(int i=0;i<k;i++){
        if(pq.size()==0){
            break;
        }
        //cout<<pq.top()<<endl;
        ans+=pq.top();
        pq.pop();
    }
    cout<<ans-1<<endl;

    return 0;
}

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