oj.uz

Submission #820144

# Submission time Handle Problem Language Result Execution time Memory
820144 2023-08-10T20:26:48 Z PurpleCrayon Dungeon 3 (JOI21_ho_t5) C++17
11 / 100
 4000 ms 3468 KB 
#include <bits/stdc++.h>
using namespace std;

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 5e2+10, MOD = 998244353;

void solve() {
    int n, m; cin >> n >> m;
    vector<ll> a(n); for (auto& x : a) cin >> x;
    vector<ll> b(n); for (auto& x : b) cin >> x;

    while (m--) {
        int l, r, cap; cin >> l >> r >> cap, --l, --r;
        deque<pair<int, ll>> st;

        ll ans = 0;
        ll sub = 0;
        for (int i = l; i < r; i++) {
            ll need = a[i], cost = b[i];
            while (sz(st) && b[st.back().first] >= cost) st.pop_back();
            st.emplace_back(i, cap + sub);

            while (sz(st) && need) {
                ll cur = min(st.front().second - sub, need); 
                ans += b[st.front().first] * cur;
                need -= cur, sub += cur;

                while (sz(st) && st.front().second == sub) st.pop_front();
            }

            if (need) {
                ans = -1;
                break;
            }
        }

        cout << ans << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 376 KB Output is correct
2 Correct 58 ms 432 KB Output is correct
3 Correct 34 ms 392 KB Output is correct
4 Correct 59 ms 372 KB Output is correct
5 Correct 49 ms 436 KB Output is correct
6 Correct 36 ms 340 KB Output is correct
7 Correct 57 ms 384 KB Output is correct
8 Correct 48 ms 440 KB Output is correct
9 Correct 34 ms 404 KB Output is correct
10 Correct 61 ms 372 KB Output is correct
11 Correct 55 ms 376 KB Output is correct
12 Correct 32 ms 376 KB Output is correct
13 Correct 48 ms 340 KB Output is correct
14 Correct 33 ms 380 KB Output is correct
15 Correct 37 ms 380 KB Output is correct
16 Correct 46 ms 420 KB Output is correct
17 Correct 38 ms 388 KB Output is correct
18 Correct 46 ms 340 KB Output is correct
19 Correct 28 ms 392 KB Output is correct
20 Correct 115 ms 500 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4048 ms 1660 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 4066 ms 3468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 376 KB Output is correct
2 Correct 58 ms 432 KB Output is correct
3 Correct 34 ms 392 KB Output is correct
4 Correct 59 ms 372 KB Output is correct
5 Correct 49 ms 436 KB Output is correct
6 Correct 36 ms 340 KB Output is correct
7 Correct 57 ms 384 KB Output is correct
8 Correct 48 ms 440 KB Output is correct
9 Correct 34 ms 404 KB Output is correct
10 Correct 61 ms 372 KB Output is correct
11 Correct 55 ms 376 KB Output is correct
12 Correct 32 ms 376 KB Output is correct
13 Correct 48 ms 340 KB Output is correct
14 Correct 33 ms 380 KB Output is correct
15 Correct 37 ms 380 KB Output is correct
16 Correct 46 ms 420 KB Output is correct
17 Correct 38 ms 388 KB Output is correct
18 Correct 46 ms 340 KB Output is correct
19 Correct 28 ms 392 KB Output is correct
20 Correct 115 ms 500 KB Output is correct
21 Execution timed out 4048 ms 1660 KB Time limit exceeded
22 Halted 0 ms 0 KB -