Submission #1066149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066149		sammyuri	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	3 ms	604 KiB

semiexpress

#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 (stderr)

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 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52