oj.uz

Submission #127693

# Submission time Handle Problem Language Result Execution time Memory
127693 2019-07-10T01:59:21 Z EntityIT Semiexpress (JOI17_semiexpress) C++14
100 / 100
 3 ms 504 KB 
#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second

using ii = pair<int, int>;
using ll = long long;
const int MAX_K = (int)3e3 + 5;
int n, m, K, a, b, c, s[MAX_K], lst[MAX_K], ans;
ll T;
priority_queue<ii> pq;

int calc (int i) {
    ll cur = 1LL * b * s[i] + 1LL * c * (lst[i] - s[i]);
    if (cur > T) return 0;
    ll ret = (T - cur) / a;
    ret = min(ret, (ll)(s[i + 1] - lst[i] - 1) );
    return (int)ret + 1;
}

int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m >> K >> a >> b >> c >> T; K -= m;
    for (int i = 1; i <= m; ++i) {
        cin >> s[i]; --s[i];
        if (s[i] && 1LL * b * s[i] <= T) ++ans;
    }

    for (int i = 1; i < m; ++i) {
        ll cur = 1LL * b * s[i];
        if (cur > T) break ;
        ll tmp = (T - cur) / a;
        tmp = min(tmp, (ll)(s[i + 1] - s[i] - 1) );
        ans += (int)tmp;
        lst[i] = s[i] + (int)tmp + 1;
        if (lst[i] != s[i + 1]) pq.push( { calc(i), i } );
    }

    while (K-- && !pq.empty() ) {
        ii tmp = pq.top(); pq.pop();
        ans += tmp.fi;
        lst[tmp.se] += tmp.fi;
        if (lst[tmp.se] != s[tmp.se + 1]) pq.push( { calc(tmp.se), tmp.se } );
    }

    cout << ans;

    return 0;
}

Subtask #1
18.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

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