oj.uz

Submission #816622

# Submission time Handle Problem Language Result Execution time Memory
816622 2023-08-09T05:55:23 Z jophyyjh Rice Hub (IOI11_ricehub) C++14
100 / 100
 14 ms 2560 KB 
/**
 * Quite trivial?
 * 
 * Time Complexity: O(R)            (two-pointer, binary search)
 * Implementation 1                 (Full solution)
*/

#include <bits/stdc++.h>
#include "ricehub.h"

typedef long long   ll;


// Calculate the cost of grabbing all rice hubs between a and b, inclusive.
inline ll calc_cost(const std::vector<ll>& prefix_sum, int a, int b) {
    int mid = (a + b) / 2, mid_val = prefix_sum[mid + 1] - prefix_sum[mid];
    ll c1 = (mid - a + 1) * mid_val - (prefix_sum[mid + 1] - prefix_sum[a]);
    ll c2 = (prefix_sum[b + 1] - prefix_sum[mid + 1]) - (b - mid) * mid_val;
    return c1 + c2;
}

int besthub(int R, int L, int X[], ll B) {
    std::vector<ll> prefix_sum(R + 1);
    prefix_sum[0] = 0;
    for (int k = 0; k < R; k++)
        prefix_sum[k + 1] = prefix_sum[k] + X[k];
    int max_rice = 0;
    for (int a = 0, b = 0; b < R; a++) {
        while (b < R && calc_cost(prefix_sum, a, b) <= B)
            b++;
        max_rice = std::max(max_rice, b - a);
    }
    return max_rice;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
25.0 / 25.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 312 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 312 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 356 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 324 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 612 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 11 ms 2480 KB Output is correct
4 Correct 14 ms 2560 KB Output is correct
5 Correct 5 ms 1132 KB Output is correct
6 Correct 4 ms 1196 KB Output is correct
7 Correct 11 ms 2244 KB Output is correct
8 Correct 8 ms 2144 KB Output is correct
9 Correct 5 ms 1192 KB Output is correct
10 Correct 6 ms 1188 KB Output is correct
11 Correct 9 ms 2556 KB Output is correct
12 Correct 11 ms 2480 KB Output is correct
13 Correct 5 ms 1236 KB Output is correct
14 Correct 4 ms 1236 KB Output is correct
15 Correct 8 ms 1872 KB Output is correct
16 Correct 7 ms 1892 KB Output is correct
17 Correct 13 ms 2260 KB Output is correct
18 Correct 8 ms 2184 KB Output is correct
19 Correct 9 ms 2324 KB Output is correct
20 Correct 10 ms 2404 KB Output is correct