Submission #1285268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285268		kaiboy	Dungeon 3 (JOI21_ho_t5)	C++20	11 / 100	25 ms	584 KiB

Main

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 3000;

int aa[N], cc[N], qu[N], qq[N];
long long ss[N + 1];

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, q; cin >> n >> q;
	for (int i = 0; i < n; i++)
		cin >> aa[i];
	for (int i = 0; i < n; i++)
		cin >> cc[i];
	for (int i = n - 1; i >= 0; i--)
		ss[i] = aa[i] + ss[i + 1];
	while (q--) {
		int l, r, a_; cin >> l >> r >> a_, l--, r--;
		int cnt = 0;
		for (int i = r - 1; i >= l; i--) {
			while (cnt && cc[i] < cc[qu[cnt - 1]])
				cnt--;
			qq[i] = cnt ? qu[cnt - 1] : r, qu[cnt++] = i;
		}
		long long ans = 0;
		for (int a = 0, i = l; i < r; i++) {
			int b = min(ss[i] - ss[qq[i]], (long long) a_);
			if (a < b)
				ans += (long long) cc[i] * (b - a), a = b;
			if (a < aa[i]) {
				ans = -1;
				break;
			}
			a -= aa[i];
		}
		cout << ans << '\n';
	}
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 31
• Subtask 4: 0 / 44