Submission #998348

#	Time	Username	Problem	Language	Result	Execution time	Memory
998348		Otalp	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	50 ms	19892 KiB

semiexpress

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll

int s[200100];



signed main(){
    int n, m, k;
    cin>>n>>m>>k;
    int a, b, c;
    cin>>a>>b>>c;
    ll t;
    cin>>t;
    for(int i=1; i<=m; i++){
        cin>>s[i];
    }
    multiset<int> q;
    int ans = -1;
    for(int i=1; i<m; i++){
        //cout<<"#####################\n";
        //cout<<s[i]<<'\n';
        if((s[i] - 1) * b > t) continue;
        if((t - (s[i] - 1) * b) / a + 1 > s[i + 1] - s[i]){
            ans += s[i + 1] - s[i];
            continue;
        } 
        ans += (t - (s[i] - 1) * b) / a + 1;
        int ls = s[i] + (t - (s[i] - 1) * b) / a;
        //cout<<ls<<'\n';
        for(int j=1; j<=k-m; j++){
            if((s[i] - 1) * b + (ls + 1 - s[i]) * c > t) break;
            int x = (t - ((s[i] - 1) * b + (ls + 1 - s[i]) * c))/a + 1;
            if(x > s[i + 1] - (ls + 1)){
                q.insert(s[i + 1] - (ls + 1));
                break;
            }
            //cout<<ls<<' '<<x<<'\n';
            q.insert(x);
            ls = ls + 1 + x - 1;
        }
    }
    if((n-1) * b <= t) ans ++;
    for(int i=0; i<k-m and q.size(); i++){
        auto it = q.end();
        it--;
        //cout<<*it<<'\n';
        ans += *it;
        q.erase(it);
    }
    cout<<ans;
}

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