Submission #1051742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051742		gagik_2007	Semiexpress (JOI17_semiexpress)	C++17	18 / 100	1 ms	348 KiB

semiexpress

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=5007;
ll n,m,k;
ll a,b,c;
ll t;
vector<ll>s;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("Binput.txt","r",stdin);
    // freopen("Boutput.txt","w",stdout);
    cin>>n>>m>>k;
    cin>>a>>b>>c;
    cin>>t;
    for(int i=0;i<m;i++){
        int x;
        cin>>x;
        s.push_back(x);
    }
    ll ans=0;
    ll cur=0;
    priority_queue<pair<ll,ll>>q;
    for(int i=0;i<m-1;i++){
        if(cur>t)break;
        ll cnt=(t-cur)/a+1;
        if(cnt<s[i+1]-s[i]){
            ans+=cnt;
            ll pos=s[i]+cnt;
            ll rem=t-cur-cnt*c;
            if(rem>=0){
                ll cnt2=rem/a+1;
                if(cnt2+pos<s[i+1]){
                    q.push({cnt2,pos});
                }
                else{
                    q.push({s[i+1]-pos,pos});
                }
            }
        }
        else{
            ans+=s[i+1]-s[i];
        }
        cur+=(s[i+1]-s[i])*b;
    }
    if(cur<=t){
        ans++;
    }
    k-=m;
    while(!q.empty()&&k>0){
        ll cnt=q.top().ff;
        ll pos=q.top().ss;
        // cout<<cnt<<" "<<pos<<endl;
        q.pop();
        ans+=cnt;
        auto it=lower_bound(s.begin(),s.end(),pos+cnt);
        if((*it)>pos+cnt){
            ll newpos=pos+cnt;
            --it;
            ll rem=t-((*it)-1)*b-(newpos-(*it))*c;
            if(rem>=0){
                ll cnt2=rem/a+1;
                ++it;
                if(cnt2+pos<(*it)){
                    q.push({cnt2,newpos});
                }
                else{
                    q.push({(*it)-newpos,newpos});
                }
            }
        }
        k--;
    }
    cout<<ans-1<<endl;
}

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