Submission #939331

#	Time	Username	Problem	Language	Result	Execution time	Memory
939331		browntoad	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	1 ms	604 KiB

semiexpress

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define RREP1(i, n) for(int i = (n); i >= 1; i--)
#define pii pair<int, int>
#define ppp pair<pii, pii>
#define ppi pair<pii, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define endl '\n'
#define IOS() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)


const ll maxn = 3e5+5;
const ll maxm = 1e4+5;
const ll mod = 1e9+7;
const ll inf = 1ll<<60;

int n, m, k;
int a, b, c;
int T;

int comp(int nx, int nv, int R){
    // if dp[nx] = nv, how much can it extend
    return min(R-nx-1, (T-nv)/a);
}
signed main(){
    IOS();
    cin>>n>>m>>k;
    cin>>a>>b>>c;
    cin>>T;

    vector<int> ex(m+1); // express

    REP(i, m){
        cin>>ex[i];
    }
    int ans = ((ex[m-1]-1)*b <= T)-1;
    priority_queue<ppp> pq;
    REP(i, m-1){ // wont calculate last one, but counted first one
        int l = ex[i], r = ex[i+1];
        int v = (ex[i]-1)*b;
        if (v > T) continue;
        ans += comp(l, v, r)+1;
        l += comp(l, v, r)+1;
        if (l < r && v+c*(l-ex[i]) <= T){
            pq.push({{comp(l, v+c*(l-ex[i]), r), v+c*(l-ex[i])}, {l, r}});
        }
    }

    k -= m;
    while(SZ(pq) && k > 0){
        ppp tp = pq.top(); pq.pop();
        int l = tp.s.f, r = tp.s.s, ext = tp.f.f, v = tp.f.s;
        ans += ext+1;

        l += ext+1;
        if (l < r && v+c*(ext+1) <= T){
            pq.push({{comp(l, v+c*(ext+1), r), v+c*(ext+1)}, {l, r}});
        }
        k--;
    }
    /*REP1(i, n){
        dp[i] = min(dp[i-1]+a, dp[i]);
        if (dp[i] <= T) ans++;
    }
    */
    cout<<ans<<endl;
}

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52