oj.uz

Submission #1066149

# Submission time Handle Problem Language Result Execution time Memory
1066149 2024-08-19T15:35:55 Z sammyuri Semiexpress (JOI17_semiexpress) C++17
100 / 100
 3 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, m, k;
ll a, b, c;
ll t;
vector<ll> express;

int _t;
struct range {
    ll length;
    ll curtime;
    ll curindex;
    int index;
    range (ll _l, ll _c, ll _i) {
        length = _l, curtime = _c, curindex = _i;
        index = _t ++;
    }
};

ll solve_nostart() {
    _t = 0;
    // can it reach the first express train?
    if ((express[0] - 1) * a > t)
        return 1 + t / a;
    // build ranges
    ll ans = express[0] - 1;
    vector<range> ranges;
    ll curtime = (express[0] - 1) * a;
    for (int i = 0; i < m; i ++) {
        ranges.push_back(range(
            express[i + 1] - express[i],
            curtime,
            1 + (t - curtime) / a
        ));
        ans += min(express[i + 1] - express[i], 1 + (t - curtime) / a);
        curtime += (express[i + 1] - express[i]) * b;
        if (curtime > t)
            break;
    }
    // take as many good ranges as possible
    for (int i = 0; i < k; i ++) {
        ll best = -1, besti = -1;
        for (int j = 0; j < ranges.size(); j ++) {
            if (ranges[j].curindex >= ranges[j].length)
                continue;
            ll starttime = ranges[j].curtime + (ranges[j].curindex * c);
            if (starttime > t)
                continue;
            ll heretake = min(ranges[j].length - ranges[j].curindex, 1 + (t - starttime) / a);
            if (heretake > best)
                best = heretake, besti = j;
        }
        if (best == -1)
            break;
        // update
        int j = besti;
        ll starttime = ranges[j].curtime + (ranges[j].curindex * c);
        ll heretake = min(ranges[j].length - ranges[j].curindex, 1 + (t - starttime) / a);
        ans += heretake;
        ranges[j].curindex += heretake;
    }
    return ans;
}

ll solve_start() {
    _t = 0;
    // build ranges
    vector<range> ranges;
    ranges.push_back(range(
        express[0] - 1,
        0,
        1 + t / c
    ));
    ll ans = min(express[0] - 1, 1 + t / c);
    ll curtime = (express[0] - 1) * c;
    for (int i = 0; i < m; i ++) {
        if (curtime > t)
            break;
        ranges.push_back(range(
            express[i + 1] - express[i],
            curtime,
            1 + (t - curtime) / a
        ));
        ans += min(express[i + 1] - express[i], 1 + (t - curtime) / a);
        curtime += (express[i + 1] - express[i]) * b;
        if (curtime > t)
            break;
    }
    // take as many good ranges as possible
    for (int i = 0; i < k - 1; i ++) {
        ll best = -1, besti = -1;
        for (int j = 0; j < ranges.size(); j ++) {
            if (ranges[j].curindex >= ranges[j].length)
                continue;
            ll starttime = ranges[j].curtime + (ranges[j].curindex * c);
            if (starttime > t)
                continue;
            ll heretake = min(ranges[j].length - ranges[j].curindex, 1 + (t - starttime) / a);
            if (heretake > best)
                best = heretake, besti = j;
        }
        if (best == -1)
            break;
        // update
        int j = besti;
        ll starttime = ranges[j].curtime + (ranges[j].curindex * c);
        ll heretake = min(ranges[j].length - ranges[j].curindex, 1 + (t - starttime) / a);
        ans += heretake;
        ranges[j].curindex += heretake;
    }
    return ans;
}
int main() {
    cin >> n >> m >> k;
    cin >> a >> b >> c;
    cin >> t;
    express.resize(m);
    k -= m;
    for (auto &aa : express)
        cin >> aa;
    express.push_back(n + 1);
    ll best = solve_nostart();
    ll best2 = 0;
    if (k > 0 && express[0] != 1)
        best2 = solve_start();
    cout << max(best, best2) - 1 << endl;
}

Compilation message

semiexpress.cpp: In function 'll solve_nostart()':
semiexpress.cpp:45:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<range>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int j = 0; j < ranges.size(); j ++) {
      |                         ~~^~~~~~~~~~~~~~~
semiexpress.cpp: In function 'll solve_start()':
semiexpress.cpp:94:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<range>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for (int j = 0; j < ranges.size(); j ++) {
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 432 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 3 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 408 KB Output is correct
30 Correct 1 ms 348 KB Output is correct