oj.uz

Submission #672805

# Submission time Handle Problem Language Result Execution time Memory
672805 2022-12-18T08:27:38 Z Cyanmond Discharging (NOI20_discharging) C++17
36 / 100
 1000 ms 177836 KB 
#include <bits/stdc++.h>

using i64 = long long;
constexpr i64 inf = 1ll << 60;

class SparseTable {
    int n;
    std::vector<int> log_table;
    std::vector<std::vector<i64>> data;

  public:
    SparseTable(std::vector<i64> vec) : n(vec.size()) {
        log_table.assign(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            log_table[i] = std::max(log_table[i], log_table[i - 1]);
            if (2 * i <= n) {
                log_table[2 * i] = log_table[i] + 1;
            }
        }

        data.resize(log_table[n] + 1);
        data[0] = vec;
        for (int d = 1; d <= log_table[n]; ++d) {
            const int w = 1 << d;
            data[d].resize(n - w + 1);
            for (int i = 0; i + w <= n; ++i) {
                data[d][i] = std::max(data[d - 1][i], data[d - 1][i + w / 2]);
            }
        }
    }

    i64 fold(int l, int r) const {
        const int w = r - l;
        const int d = log_table[w];
        return std::max(data[d][l], data[d][r - (1 << d)]);
    }
};

int main() {
    int N;
    std::cin >> N;
    std::vector<i64> T(N);
    for (auto &e : T) {
        std::cin >> e;
    }
    const auto st = SparseTable(T);

    auto cost = [&](const int l, const int r) {
        return (N - l) * st.fold(l, r);
    };

    std::vector<i64> dp(N + 1, inf);
    dp[0] = 0;

    auto dist = [&](const int l, const int r) {
        return dp[l] + cost(l, r);
    };

    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            dp[j] = std::min(dp[j], dist(i, j));
        }
    }

    std::cout << dp[N] << std::endl;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 300 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 300 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 304 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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 436 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 4 ms 444 KB Output is correct
11 Correct 4 ms 340 KB Output is correct
12 Correct 6 ms 452 KB Output is correct
13 Correct 3 ms 436 KB Output is correct
14 Correct 4 ms 432 KB Output is correct
15 Correct 3 ms 468 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 3 ms 436 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 4 ms 444 KB Output is correct
11 Correct 4 ms 340 KB Output is correct
12 Correct 6 ms 452 KB Output is correct
13 Correct 3 ms 436 KB Output is correct
14 Correct 4 ms 432 KB Output is correct
15 Correct 3 ms 468 KB Output is correct
16 Execution timed out 1081 ms 173308 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 177836 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 300 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 300 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 304 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 4 ms 468 KB Output is correct
16 Correct 4 ms 340 KB Output is correct
17 Correct 3 ms 432 KB Output is correct
18 Correct 3 ms 340 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 3 ms 436 KB Output is correct
21 Correct 3 ms 340 KB Output is correct
22 Correct 4 ms 340 KB Output is correct
23 Correct 4 ms 340 KB Output is correct
24 Correct 4 ms 444 KB Output is correct
25 Correct 4 ms 340 KB Output is correct
26 Correct 6 ms 452 KB Output is correct
27 Correct 3 ms 436 KB Output is correct
28 Correct 4 ms 432 KB Output is correct
29 Correct 3 ms 468 KB Output is correct
30 Correct 3 ms 340 KB Output is correct
31 Correct 4 ms 556 KB Output is correct
32 Correct 3 ms 340 KB Output is correct
33 Correct 4 ms 340 KB Output is correct
34 Correct 5 ms 428 KB Output is correct
35 Correct 3 ms 340 KB Output is correct
36 Correct 4 ms 340 KB Output is correct
37 Correct 4 ms 360 KB Output is correct
38 Correct 3 ms 340 KB Output is correct
39 Correct 4 ms 340 KB Output is correct
40 Correct 3 ms 340 KB Output is correct
41 Correct 3 ms 432 KB Output is correct
42 Correct 4 ms 436 KB Output is correct
43 Correct 3 ms 432 KB Output is correct
44 Correct 4 ms 340 KB Output is correct
45 Correct 3 ms 348 KB Output is correct
46 Correct 3 ms 340 KB Output is correct
47 Correct 4 ms 340 KB Output is correct
48 Correct 3 ms 440 KB Output is correct
49 Correct 5 ms 436 KB Output is correct
50 Correct 3 ms 340 KB Output is correct

Subtask #6
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 300 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 300 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 304 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 4 ms 468 KB Output is correct
16 Correct 4 ms 340 KB Output is correct
17 Correct 3 ms 432 KB Output is correct
18 Correct 3 ms 340 KB Output is correct
19 Correct 3 ms 340 KB Output is correct
20 Correct 3 ms 436 KB Output is correct
21 Correct 3 ms 340 KB Output is correct
22 Correct 4 ms 340 KB Output is correct
23 Correct 4 ms 340 KB Output is correct
24 Correct 4 ms 444 KB Output is correct
25 Correct 4 ms 340 KB Output is correct
26 Correct 6 ms 452 KB Output is correct
27 Correct 3 ms 436 KB Output is correct
28 Correct 4 ms 432 KB Output is correct
29 Correct 3 ms 468 KB Output is correct
30 Execution timed out 1081 ms 173308 KB Time limit exceeded
31 Halted 0 ms 0 KB -