제출 #1217896

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1217896		trimkus	Fish 3 (JOI24_fish3)	C++20	9 / 100	2095 ms	6316 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = double;

int main() {
	//~ ofstream cout("out.txt");
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	ll d;
	cin >> n >> d;
	vector<ll> a(n);
	vector<ll> ps(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		ps[i] += a[i];
		if (i) ps[i] += ps[i - 1];
	}
	vector<int> left(n, -1);
	for (int i = 0; i < n; ++i) {
		left[i] = (a[i] == 0 ? i : -1);
		if (i) left[i] = max(left[i], left[i - 1]);
	}
	int q;
	cin >> q;
	while (q--) {
		int l, r;
		cin >> l >> r;
		--l; --r;
		ll take = a[r];
		ll res = 0;
		bool ok = true;
		for (int i = r - 1; i >= l; --i) {
			ll left = 0, right = (a[i]) / d;
			ll now = -1;
			//~ cerr << take << " -> ";
			while (left <= right) {
				ll mid = (left + right) / 2;
				ll na = a[i] - mid * d;
				if (na <= take) {
					right = mid - 1;
					now = mid;
				} else {
					left = mid + 1;
				}
			}
			if (now == -1) {
				ok = false;
				break;
			}
			res += now;
			take = a[i] - now * d;
		}
		//~ cerr << "res = ";
		if (!ok) cout << "-1\n";
		else cout << res << "\n";
	}
}

• Subtask 1: 9 / 9
• Subtask 2: 0 / 7
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36