Submission #938017

#	Time	Username	Problem	Language	Result	Execution time	Memory
938017		zwezdinv	Dungeon 3 (JOI21_ho_t5)	C++17	11 / 100	4038 ms	4572 KiB

Main

#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 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 31
• Subtask 4: 0 / 44