oj.uz

Submission #87893

# Submission time Handle Problem Language Result Execution time Memory
87893 2018-12-03T03:17:16 Z tieunhi Semiexpress (JOI17_semiexpress) C++14
100 / 100
 3 ms 980 KB 
#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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 2 ms 476 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 2 ms 560 KB Output is correct
7 Correct 2 ms 564 KB Output is correct
8 Correct 2 ms 572 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 2 ms 476 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 2 ms 560 KB Output is correct
7 Correct 2 ms 564 KB Output is correct
8 Correct 2 ms 572 KB Output is correct
9 Correct 2 ms 576 KB Output is correct
10 Correct 2 ms 580 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 2 ms 592 KB Output is correct
14 Correct 3 ms 596 KB Output is correct
15 Correct 2 ms 676 KB Output is correct
16 Correct 2 ms 680 KB Output is correct
17 Correct 3 ms 812 KB Output is correct
18 Correct 2 ms 812 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 2 ms 476 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 2 ms 560 KB Output is correct
7 Correct 2 ms 564 KB Output is correct
8 Correct 2 ms 572 KB Output is correct
9 Correct 2 ms 576 KB Output is correct
10 Correct 2 ms 580 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 2 ms 592 KB Output is correct
14 Correct 3 ms 596 KB Output is correct
15 Correct 2 ms 676 KB Output is correct
16 Correct 2 ms 680 KB Output is correct
17 Correct 3 ms 812 KB Output is correct
18 Correct 2 ms 812 KB Output is correct
19 Correct 3 ms 812 KB Output is correct
20 Correct 3 ms 812 KB Output is correct
21 Correct 2 ms 812 KB Output is correct
22 Correct 2 ms 812 KB Output is correct
23 Correct 3 ms 900 KB Output is correct
24 Correct 2 ms 920 KB Output is correct
25 Correct 2 ms 920 KB Output is correct
26 Correct 2 ms 920 KB Output is correct
27 Correct 2 ms 964 KB Output is correct
28 Correct 3 ms 980 KB Output is correct
29 Correct 2 ms 980 KB Output is correct
30 Correct 2 ms 980 KB Output is correct