oj.uz

Submission #213637

# Submission time Handle Problem Language Result Execution time Memory
213637 2020-03-26T09:59:16 Z PeppaPig Semiexpress (JOI17_semiexpress) C++14
100 / 100
 6 ms 512 KB 
#include <bits/stdc++.h>

#define long long long

using namespace std;

const int N = 3e3+5;

struct item {
    long cnt, idx; int pos;
    item(long cnt, long idx, int pos) : cnt(cnt), idx(idx), pos(pos) {}
    friend bool operator<(const item &a, const item &b) {
        return a.cnt < b.cnt;
    }
};

int n, m, k;
long A, B, C, T, ans;
long st[N], dist[N];

long get_cnt(int i, long l, long r) {
    long t = (l - st[i]) * C + dist[i];
    if(t > T) return 0;
    return min((T - t) / A + 1, r - l + 1);
}

int main() {
    scanf("%d %d %d", &n, &m, &k); 
    scanf("%lld %lld %lld %lld", &A, &B, &C, &T);
    for(int i = 1; i <= m; i++) {
        scanf("%lld", st + i);
        if(i > 1) dist[i] = B * (st[i] - st[i-1]) + dist[i-1];
    }
    if(dist[m] <= T) ++ans;
    priority_queue<item> Q;
    for(int i = 1; i < m; i++) if(dist[i] <= T) {
        if(dist[i] + (st[i + 1] - st[i] - 1) * A <= T) {
            ans += st[i + 1] - st[i];
            continue;
        }
        long add = (T - dist[i]) / A + 1;
        ans += add;
        Q.emplace(get_cnt(i, st[i] + add, st[i + 1] - 1), st[i] + add, i);
    }
    k -= m;
    for(int i = 1; i <= k; i++) if(!Q.empty()) {
        item now = Q.top(); Q.pop();
        ans += now.cnt;
        long pos = now.idx + now.cnt;
        if(pos >= st[now.pos + 1]) continue;
        Q.emplace(get_cnt(now.pos, pos, st[now.pos + 1] - 1), pos, now.pos);   
    }
    printf("%lld\n", ans - 1);

    return 0;
}

Compilation message

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &k); 
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld %lld %lld", &A, &B, &C, &T);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", st + i);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
52.0 / 52.0

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