oj.uz

Submission #938017

# Submission time Handle Problem Language Result Execution time Memory
938017 2024-03-04T17:44:57 Z zwezdinv Dungeon 3 (JOI21_ho_t5) C++17
11 / 100
 4000 ms 4572 KB 
#include <bits/stdc++.h>


int main() {
        std::cin.tie(nullptr)->sync_with_stdio(false);

        int n, m;
        std::cin >> n >> m;
        std::vector<int> a(n), b(n);
        for (auto& i : a) std::cin >> i;
        for (auto& i : b) std::cin >> i;
        while (m--) {
                int l, r, u;
                std::cin >> l >> r >> u;
                l--, r--;
                std::multiset<std::pair<int, int>> st;
                long long ans = 0;
                int cur = 0;
                for (int i = l; i < r; ++i) {
                        if (a[i] > u) {
                                ans = -1;
                                break;
                        }
                        cur += u;
                        st.emplace(b[i], u);
                        while (cur > u) {
                                auto [x, y] = *--st.end();
                                st.erase(--st.end());
                                int mn = std::min(y, cur - u);
                                cur -= mn;
                                y -= mn;
                                if (y) {
                                        st.emplace(x, y);
                                }
                        }
                        int qq = a[i];
                        while (qq) {
                                auto [x, y] = *st.begin();
                                st.erase(st.begin());
                                int mn = std::min(y, qq);
                                qq -= mn;
                                y -= mn;
                                cur -= mn;
                                ans += 1ll * mn * x;
                                if (y) {
                                        st.emplace(x, y);
                                }
                        }
                }
                std::cout << ans << std::endl;
        }
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 348 KB Output is correct
2 Correct 469 ms 856 KB Output is correct
3 Correct 206 ms 604 KB Output is correct
4 Correct 400 ms 560 KB Output is correct
5 Correct 463 ms 604 KB Output is correct
6 Correct 246 ms 816 KB Output is correct
7 Correct 396 ms 792 KB Output is correct
8 Correct 467 ms 712 KB Output is correct
9 Correct 236 ms 348 KB Output is correct
10 Correct 356 ms 576 KB Output is correct
11 Correct 413 ms 604 KB Output is correct
12 Correct 202 ms 596 KB Output is correct
13 Correct 365 ms 572 KB Output is correct
14 Correct 211 ms 348 KB Output is correct
15 Correct 220 ms 348 KB Output is correct
16 Correct 459 ms 720 KB Output is correct
17 Correct 257 ms 348 KB Output is correct
18 Correct 308 ms 572 KB Output is correct
19 Correct 145 ms 572 KB Output is correct
20 Correct 1354 ms 904 KB Output is correct

Subtask #2
0 / 14.0

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

Subtask #3
0 / 31.0

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

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 348 KB Output is correct
2 Correct 469 ms 856 KB Output is correct
3 Correct 206 ms 604 KB Output is correct
4 Correct 400 ms 560 KB Output is correct
5 Correct 463 ms 604 KB Output is correct
6 Correct 246 ms 816 KB Output is correct
7 Correct 396 ms 792 KB Output is correct
8 Correct 467 ms 712 KB Output is correct
9 Correct 236 ms 348 KB Output is correct
10 Correct 356 ms 576 KB Output is correct
11 Correct 413 ms 604 KB Output is correct
12 Correct 202 ms 596 KB Output is correct
13 Correct 365 ms 572 KB Output is correct
14 Correct 211 ms 348 KB Output is correct
15 Correct 220 ms 348 KB Output is correct
16 Correct 459 ms 720 KB Output is correct
17 Correct 257 ms 348 KB Output is correct
18 Correct 308 ms 572 KB Output is correct
19 Correct 145 ms 572 KB Output is correct
20 Correct 1354 ms 904 KB Output is correct
21 Execution timed out 4038 ms 2248 KB Time limit exceeded
22 Halted 0 ms 0 KB -