oj.uz

Submission #412821

# Submission time Handle Problem Language Result Execution time Memory
412821 2021-05-27T15:48:07 Z Ozy Semiexpress (JOI17_semiexpress) C++17
100 / 100
 2 ms 460 KB 
#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.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 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 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 2 ms 460 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 2 ms 332 KB Output is correct
27 Correct 1 ms 460 KB Output is correct
28 Correct 1 ms 460 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 204 KB Output is correct