Submission #1282746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282746		kaiboy	Dungeon 3 (JOI21_ho_t5)	C++20	11 / 100	103 ms	812 KiB

Main

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 3000;

int aa[N], bb[N];
long long xx[N + 2], yy[N + 2];

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 >> bb[i];
	while (q--) {
		int l, r, a_; cin >> l >> r >> a_, l--, r -= 2;
		bool yes = true;
		for (int i = l; i <= r; i++)
			if (aa[i] > a_) {
				yes = false;
				break;
			}
		if (!yes) {
			cout << "-1\n";
			continue;
		}
		int l_ = 0, r_ = 0; long long x_ = 0;
		xx[r_] = a_, yy[r_] = 0, r_++;
		xx[r_] = 0, yy[r_] = 0, r_++;
		for (int i = r; i >= l; i--) {
			int a = aa[i], b = bb[i];
			while (x_ + xx[l_] > a_ - a)
				l_++;
			x_ += a;
			if (x_ + xx[l_] < a_) {
				long long d = (yy[l_] - yy[l_ - 1]) / (xx[l_ - 1] - xx[l_]);
				l_--, xx[l_] = a_ - x_, yy[l_] = yy[l_ + 1] - d * (xx[l_] - xx[l_ + 1]);
			}
			while (r_ - l_ >= 2 && (yy[r_ - 1] - yy[r_ - 2]) / (xx[r_ - 2] - xx[r_ - 1]) >= b)
				r_--;
			xx[r_] = -x_, yy[r_] = yy[r_ - 1] + b * (xx[r_ - 1] - xx[r_]), r_++;
		}
		cout << yy[r_ - 1] << '\n';
	}
	return 0;
}

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