oj.uz

Submission #146222

# Submission time Handle Problem Language Result Execution time Memory
146222 2019-08-22T21:05:57 Z osaaateiasavtnl Semiexpress (JOI17_semiexpress) C++14
100 / 100
 3 ms 504 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
const int N = 3001, INF = 1e9 + 7;
int blet, EX, SEX, A, B, C, T;
int s[N];
//A, B, C - local, express, semiexpress
int getime(int p) { int i = upper_bound(s, s + EX, p) - s - 1; return (s[i] - 1) * B + (p - s[i]) * C; }
int next(int p) { return upper_bound(s, s + EX, p) - s; }
int getr(int p) { return p + (T - getime(p)) / A; }
int get(int p) { return min(getr(p), s[next(p)] - 1) - p + 1; }
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> blet >> EX >> SEX >> A >> B >> C >> T;
    for (int i = 0; i < EX; ++i) cin >> s[i];
    priority_queue <ii> q;
    int ans = (getime(s[EX - 1]) <= T);
    for (int i = 0; i + 1 < EX; ++i) {
        if (getime(s[i]) <= T) {
            ans += get(s[i]);
            int l = getr(s[i]) + 1;
            if (l < s[i + 1] && getime(l) <= T) q.emplace(get(l), l);
        }
    }
    for (int it = 0; it < SEX - EX && q.size(); ++it) {
        int p = q.top().second; q.pop(); ans += get(p);
        int l = getr(p) + 1;
        if (l < s[next(p)] && getime(l) <= T) q.emplace(get(l), l);
    }
    cout << ans - 1 << '\n';
}

Subtask #1
18.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 504 KB Output is correct
22 Correct 3 ms 376 KB Output is correct
23 Correct 3 ms 376 KB Output is correct
24 Correct 3 ms 376 KB Output is correct
25 Correct 3 ms 376 KB Output is correct
26 Correct 3 ms 376 KB Output is correct
27 Correct 3 ms 504 KB Output is correct
28 Correct 3 ms 504 KB Output is correct
29 Correct 2 ms 376 KB Output is correct
30 Correct 2 ms 376 KB Output is correct