Submission #501494

#	Time	Username	Problem	Language	Result	Execution time	Memory
501494		Lobo	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	1 ms	332 KiB

semiexpress

#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 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52