Submission #1180121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180121		patgra	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	0 ms	328 KiB

semiexpress

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    ll n, m, k;
    cin >> n >> m >> k;
    k -= m;
    ll a, b, c;
    cin >> a >> b >> c;
    ll t;
    cin >> t;
    vector<ll> s(m), entry(m - 1, 0), unreachable(m - 1, 0), inside(m - 1, 0);
    rep(i, 0ll, m) cin >> s[i];
    priority_queue<pair<int, int>> Q;
    ll ans = 0;
    rep(i, 0ll, m - 1) {
        entry[i] = (s[i] - 1) * b;
        inside[i] = s[i + 1] - s[i] - 1;
        ll reachable = max(0ll, min(inside[i], (t - entry[i]) / a));
        unreachable[i] = inside[i] - reachable;
        ans += reachable + (entry[i] < t);
        DC << "interval " << i << " entry " << entry[i] << " inside " << inside[i] << " unreachable " << unreachable[i] << eol;
        if(t >= entry[i] + c * (reachable + 1)) {
            Q.push({min(unreachable[i], (t - (entry[i] + c * (reachable + 1))) / a + 1), i});
            DC << " adding at " << i << " adds " << min(unreachable[i], (t - (entry[i] + c * (reachable + 1))) / a + 1) << eol;
        }
    }
    ans += (s[m - 1] - 1) * b < t;
    DC << "  " << ans << eol;
    rep(_, 0, k) {
        if(Q.empty()) break;
        auto [add, i] = Q.top();
        Q.pop();
        DC << "doing adding at " << i << eol;
        ans += add;
        unreachable[i] -= add;
        if(t >= entry[i] + c * (inside[i] - unreachable[i] + 1)) {
            Q.push({min(unreachable[i], (t - (entry[i] + c * (inside[i] - unreachable[i] + 1))) / a + 1), i});
            DC << " after it adds " << min(unreachable[i], (t - (entry[i] + c * (inside[i] - unreachable[i] + 1))) / a + 1) << eol;
        }
    DC << "  " << ans << eol;
    }
    cout << ans - 1 << '\n';
}

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