oj.uz

Submission #376467

# Submission time Handle Problem Language Result Execution time Memory
376467 2021-03-11T14:16:20 Z smjleo Semiexpress (JOI17_semiexpress) C++14
100 / 100
 37 ms 492 KB 
#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.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

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