oj.uz

Submission #412811

# Submission time Handle Problem Language Result Execution time Memory
412811 2021-05-27T15:38:10 Z Ozy Semiexpress (JOI17_semiexpress) C++17
18 / 100
 1 ms 312 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 < 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;
}

Compilation message

semiexpress.cpp: In member function 'bool x::operator<(const x&) const':
semiexpress.cpp:17:22: warning: self-comparison always evaluates to false [-Wtautological-compare]
   17 |         return largo < largo;
      |                ~~~~~ ^ ~~~~~

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 312 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #2
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 312 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 312 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 Incorrect 1 ms 204 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
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 312 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 312 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 Incorrect 1 ms 204 KB Output isn't correct
16 Halted 0 ms 0 KB -