Submission #127693

#	Time	Username	Problem	Language	Result	Execution time	Memory
127693		EntityIT	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	3 ms	504 KiB

semiexpress

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