oj.uz

Submission #501494

# Submission time Handle Problem Language Result Execution time Memory
501494 2022-01-03T13:41:25 Z Lobo Semiexpress (JOI17_semiexpress) C++17
100 / 100
 1 ms 332 KB 
#include<bits/stdc++.h>
using namespace std;

/*for ordered_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
*/

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 3300

ll n, m, k, tl, ts, te, T, s[maxn];

void solve() {
    cin >> n >> m >> k;
    cin >> tl >> te >> ts;
    cin >> T;
    k-= m;

    for(ii i = 1; i <= m; i++) {
        cin >> s[i];
    }

    priority_queue<pair<ll,pair<ll,ll>>> pq;
    ll ans = -1;
    for(ii i = 1; i < m; i++) {
        ll tot = s[i+1]-s[i];
        ll t = (s[i]-1)*te;
        if(t > T) continue;

        //pra chegar em s[i]+x -> x*tl;
        //t+x*tl <= T ->x*tl <= T-t -> x <= (T-t)/tl;
        ll qtd = min(tot,(T-t)/tl + 1);
        // cout << s[i] << " " << qtd << " " << tot << " " << t << endl;
        tot-= qtd;
        ans+= qtd;

        //calcular o qtd se colocar mais um
        t = t+(qtd)*ts;
        if(t > T) continue;
        qtd = min(tot,(T-t)/tl + 1);
        // cout << s[i] << " " << qtd << " " << tot-qtd << " " << t << endl;

        pq.push(mp(qtd,mp(tot-qtd,t)));
    }

    if((n-1)*te <= T) ans++;

    while(k-- && pq.size()) {
        ll qtd = pq.top().fr;
        ll tot = pq.top().sc.fr;
        ll t = pq.top().sc.sc;
        pq.pop();

        ans+= qtd;

        // cout << qtd << " " << tot << " " << t << endl;

        t = t+(qtd)*ts;
        if(t > T) continue;

        qtd = min(tot,(T-t)/tl + 1);
        pq.push(mp(qtd,mp(tot-qtd,t)));

    }

    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    ii tt = 1;
    // cin >> tt;
    while(tt--) solve();

}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

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