제출 #129594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
129594		miguel	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	3 ms	508 KiB

semiexpress

#include<bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define int ll
#define sz size()
#define x first
#define y second
#define pi pair <int, int>
#define pii pair <int, pi>
#define vi vector <int>
const ll mod = 1e9 + 7;
int m, k, a, b, c, s[30005], lst[30005];
ll n, t, ans;
priority_queue<pi> p;

int calc(int i){
    ll cur=1LL*s[i]*b+1LL*c*(lst[i]-s[i]);
    if(cur>t) return 0;
    ll ans1=(t-cur)/a;
    ans1=min(ans1, s[i+1]-lst[i]-1);
    return (ans1+1);
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n>>m>>k>>a>>b>>c>>t;
    k-=m;
    for(int i=1; i<=m; i++){
        cin>>s[i];
        s[i]--;
        if(s[i] && 1LL*s[i]*b<=t) ans++;
    }
    //cout<<ans<<" ";
    for(int i=1; i<m; i++){
        ll cur=1LL*s[i]*b;
        if(cur>t) break;
        ll tm=(t-cur)/a;
        tm=min(tm, s[i+1]-s[i]-1);
        ans+=tm;
        lst[i]=s[i]+tm+1;
        if(lst[i]!=s[i+1]) p.push({calc(i), i});
    }
    //for(int i=1; i<=m; i++) cout<<lst[i]<<" "; cout<<endl;
    while(k-- && !p.empty()){
        pi tm=p.top();
        p.pop();
        //cout<<ans<<" ";
        ans+=tm.x;
        lst[tm.y]+=tm.x;
        if(lst[tm.y]!=s[tm.y+1]) p.push({calc(tm.y), tm.y});
    }
    cout<<ans;
}

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