Submission #1293491

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293491		fairkrash	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	7 ms	580 KiB

semiexpress

#include <bits/stdc++.h>

#include <random>

using namespace std;
using ll = long long;
using ld = long double;

ll INF = 1e18 + 10;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll n, m, k;
    cin >> n >> m >> k;
    ll a, b, c;
    cin >> a >> b >> c;
    ll h = k - m;
    ll t;
    cin >> t;
    vector<ll> z(m);
    for (ll j = 0; j < m; j++) {
        cin >> z[j];
    }
    ll ans = 0;
    if ((z[m - 1] - 1) * b <= t) {
        ans++;
    }
    vector<pair<ll, pair<ll, ll>>> pos;
    for (ll i = 0; i < m - 1; i++) {
        if ((z[i] - 1) * b > t) continue;
        ans++;
        ll ost = t - ((z[i] - 1) * b);
        ans += min(ost / a, z[i + 1] - z[i] - 1);
        pos.push_back({(z[i] - 1) * b, {z[i], z[i + 1]}});
    }
    for (ll i = 0; i < k - m; i++) {
        ll mx = 0;
        ll ind = -1;
        for (ll j = 0; j < pos.size(); j++) {
            if (pos[j].first > t)continue;
            ll ost = t - pos[j].first;
            ll last = ost / a;
            if (last + pos[j].second.first >= pos[j].second.second - 1) {
                continue;
            }
            ll d = pos[j].first + (last + 1) * c;
            if (d > t) {
                continue;
            }
            ll cur = (t - d) / a;
            ll cnt = min(1 + cur, (pos[j].second.second - 1) - (last + pos[j].second.first));
            if (mx < cnt) {
                mx = cnt;
                ind = j;
            }
//            if (cur + last + 1 + pos[j].second.first >= pos[j].second.second - 1) {
//            }
        }
        if (mx == 0) {
            break;
        }
        ans += mx;
        ll j = ind;
        ll ost = t - pos[j].first;
        ll last = ost / a;
        if (last + pos[j].second.first >= pos[j].second.second - 1) {
            continue;
        }
        ll d = pos[j].first + (last + 1) * c;
        if (d > t) {
            continue;
        }
        ll cur = (t - d) / a;
        ll cnt = min(1 + cur, (pos[j].second.second - 1) - last + pos[j].second.first);
        if (cur + last + 1 + pos[j].second.first >= pos[j].second.second - 1) {
            pos[j].first = INF;
        } else {
            pos[j].first += (last + 1) * c;
            pos[j].second.first += last + 1;
        }
    }
    cout << ans - 1;
}
// 300 8 16
// 345678901 123456789 234567890
// 12345678901
// 1
// 10
// 77
// 82
// 137
// 210
// 297
// 300

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