Submission #412821

#	Time	Username	Problem	Language	Result	Execution time	Memory
412821		Ozy	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	2 ms	460 KiB

semiexpress

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
 
struct x{
    lli pos;
    lli largo;
    lli tiempo;
 
    bool operator < (const x &a)
    const {
        return largo < a.largo;
    }
};
 
lli n,m,k,A,B,C,T,a,res, pos;
x act, tmp;
set<lli> paradas;
set<lli>::iterator it;
priority_queue<x> cola;
 
lli siguiente(lli pos, lli ti) {
    lli a,b;
 
    if (ti >= T) return 0;
 
    a = ((T - ti)/A) + 1;
    b = (*paradas.upper_bound(pos)) - pos;
 
    if (b <= a) return 0;
    else return pos + a;
}
 
lli cuantos(lli pos, lli ti){
    lli a,b;
 
    if (ti >= T) return 0;
 
    a = ((T - ti)/A);
    b = (*paradas.upper_bound(pos)) - 1 - pos;
 
    return min(a, b);
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> n >> m >> k;
    cin >> A >> B >> C;
    cin >> T;
 
    rep(i,1,m) {
        cin >> a;
        paradas.insert(a);
    }
    paradas.insert(n+1);
 
    res = 0;
    for(auto p : paradas){
        if (p == n + 1) break;
        if ((p - 1) * B > T) break;
 
        res += cuantos(p, (p - 1) * B) + 1;
        //debugsl(p);
        //debug(res);
        pos = siguiente(p, (p - 1) * B);
        if (pos){
            act.pos = pos;
            act.tiempo = (p - 1) * B + (pos - p) * C;
            act.largo = cuantos(act.pos, act.tiempo);
            if (act.tiempo <= T) cola.push(act);
        }
    }
 
    k -= m;
 
    while (k-- && !cola.empty()){
        act = cola.top();
        cola.pop();
        res += act.largo + 1;
        //debugsl(res);
        //debugsl(pos);
        //debugsl(act.pos);
        //debugsl(act.tiempo);
        //debug(act.largo);
        pos = siguiente(act.pos, act.tiempo);
        if (pos){
            tmp.pos = pos;
            tmp.tiempo = act.tiempo + (pos - act.pos) * C;
            tmp.largo = cuantos(tmp.pos, tmp.tiempo);
            if (tmp.tiempo <= T) cola.push(tmp);
        }
    }
 
    res--;
    cout << res;
 
    return 0;
}

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