Submission #87893

#	Time	Username	Problem	Language	Result	Execution time	Memory
87893		tieunhi	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	3 ms	980 KiB

semiexpress

#include <bits/stdc++.h>
#define pii pair<ll, ll>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define ll long long
#define mid (r + l)/2
#define N 30005
#define LN 19
#define maxc 1000000007

using namespace std;

ll n, m, k, A, B, C, T, S[N], res;
priority_queue<pair<pii, pii> >q;
void push(ll x, ll limit, ll time)
{
    if (x > limit || time < 0) return;
    ll stationCome = time/A;

    ll cur;
    if (x + stationCome <= limit)
        cur = stationCome + 1;
    else
        cur = limit - x + 1;
    q.push(mp(mp(cur, time), mp(x, limit)));
}
void get()
{
    auto z = q.top();
    res += z.F.F;
    q.pop();
    ll x = z.S.F;
    ll limit = z.S.S;
    ll timeLeft = z.F.S;

    ll stationCome = timeLeft/A;
    push(x + stationCome + 1, limit, timeLeft - (stationCome+1)*C);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    cin >> n >> m >> k >> A >> B >> C >> T; k -= m;
    S[m+1] = n+1;
    FOR(i, 1, m) cin >> S[i];
    FOR(i, 1, m)
    {
        ll timeLeft = T - (S[i]-1)*B;
        if (timeLeft < 0) break;
        ll stationCome = timeLeft/A;

        if (S[i] + stationCome < S[i+1])
        {
            res += stationCome + 1;
            push(S[i] + stationCome + 1, S[i+1] - 1, timeLeft - (stationCome+1)*C);
        }
        else res += abs(S[i+1] - S[i]);
    }
    while (!q.empty() && k--)
    {
        get();
    }
    cout <<res - 1;
}

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