Submission #376467

#	Time	Username	Problem	Language	Result	Execution time	Memory
376467		smjleo	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	37 ms	492 KiB

semiexpress

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#define int long long
#define nl '\n'
#define io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
const int mod = 1000000007, mod2 = 998244353;

// change this
const int N = 3005;

int n, m, k, a, b, c, t, ans;
set< pair<int, int> > s;

signed main() {
    io;
    cin >> n >> m >> k;
    cin >> a >> b >> c;
    k -= m;
    cin >> t;
    
    for (int i=0; i<m; i++) {
        int temp;
        cin >> temp;
        s.insert({temp-1, 0});
    }

    // first, let's get current number without adding more
    for (auto it = (++s.begin()); it != s.end(); ++it) {
        // how many can we get from [lb, ub)?
        int lb = (*(--it)).first; it++;
        int ub = (*it).first;

        int d = min((t - b*lb) / a, (ub-lb-1));     // maximum d such that we can go to lb + d
        if (lb * b + d * c > t) continue;
        if (d >= 0) ans += (d+1);
    }

    if (b * (*(--s.end())).first <= t) ans++;   // can reach very end also

    // cout << "INITIAL " << ans << nl;

    // now, for each k, find best.
    while (k--) {
        pair<int, int> bestin = {-1, -1};
        int best = - 1;
        for (auto it = (++s.begin()); it != s.end(); ++it) {
            // how many can we gain?
            auto lb = *(--it); it++;
            auto ub = *it;

            if (ub.second) continue;    // otherwise we would've added this alr

            // first, where should we add?
            int ni = lb.second + ((t - b*lb.first - c*lb.second) / a) + 1;
            if (lb.first * b + ni * c > t) continue;  // we can't come here anyway
            if (lb.first + ni >= ub.first) continue; // saturated liao

            // we should add at ni. how many new stuff does that give us?
            int d = (t - b*lb.first - c*ni) / a + 1;
            d = min(d, ub.first - (lb.first + ni));
            if (d <= 0) continue;

            // it gives us d more things!
            if (best < d) {
                best = d;
                bestin = {lb.first, ni};
            }
        }
        if (best == -1) break;
        ans += best;
        s.insert(bestin);
        // cout << bestin.first << ' ' << bestin.second << ' ' << best << nl;
    }

    cout << ans-1 << nl;
}

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