oj.uz

Submission #516695

# Submission time Handle Problem Language Result Execution time Memory
516695 2022-01-21T20:29:11 Z Giantpizzahead Semiexpress (JOI17_semiexpress) C++17
100 / 100
 1 ms 452 KB 
/*
Solution: 
Runtime: 
*/

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define sz(x) ((int) x.size())
#define all(x) x.begin(), x.end()
#define debug if (true) cerr
using ll = long long;

int N, M, K;
ll A, B, C, T, ans;
vector<int> S;
vector<ll> timeS;

struct Loc {
    int toAdd;
    int i, l, r;
    ll t;
    bool operator<(const Loc& o) const {
        if (toAdd != o.toAdd) return toAdd > o.toAdd;
        else return i < o.i;
    }
};
set<Loc> improve;

/*
l = Location of last non-local train
r = One index before the next express train
t = Time at location l
*/
void calcRange(int i, int l, int r, ll t) {
    // cout << "calc " << i << " " << l << " " << r << " " << t << '\n';
    // Find number reachable by local
    ll reachable = min((T-t) / A, (ll) (r-l));
    // cout << "reachable " << reachable << " at " << l << '\n';
    ans += reachable;
    int newLoc = l + 1 + reachable;

    ll newT = t + C * (newLoc-l);
    if (reachable < r-l && newT <= T) {
        // Could improve with a semiexpress train; by how much?
        int numLeft = (r-l) - reachable - 1;
        ll newReachable = min((T-newT) / A, (ll) numLeft);
        int toAdd = 1 + newReachable;
        improve.insert({toAdd, i, newLoc, r, newT});
        // cout << "improve " << toAdd << " at " << l << '\n';
    }
}

void solve() {
    cin >> N >> M >> K;
    cin >> A >> B >> C;
    cin >> T;
    ll currT = 0;
    rep(i, 0, M) {
        int x; cin >> x; x--;
        S.push_back(x);
        if (i != 0) currT += B * (S[i]-S[i-1]);
        timeS.push_back(currT);
    }
    ans = -1;  // Not counting station 1
    rep(i, 0, M) {
        if (timeS[i] <= T) ans++;  // Can reach express station
        else break;
        if (i == M-1) break;
        calcRange(i, S[i], S[i+1]-1, timeS[i]);
    }
    // Improve while possible
    rep(i, 0, K-M) {
        if (improve.empty()) break;
        Loc l = *improve.begin();
        improve.erase(l);
        ans++;
        calcRange(l.i, l.l, l.r, l.t);
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 312 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 316 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 312 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 1 ms 308 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 312 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 312 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 316 KB Output is correct
9 Correct 1 ms 312 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 1 ms 308 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 328 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 452 KB Output is correct
24 Correct 1 ms 316 KB Output is correct
25 Correct 1 ms 324 KB Output is correct
26 Correct 1 ms 356 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 452 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 308 KB Output is correct