Submission #1213977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213977		k1r1t0	Mizuyokan 2 (JOI23_mizuyokan2)	C++20	15 / 100	4094 ms	3960 KiB

mizuyokan2

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 251000;
const int Q = 51000;

int n, q, l[N], a[N], dp[N];

int solve() {
	for (int i = 0; i <= n + 1; i++)
		dp[i] = 0;
	dp[1] = 1;
	for (int i = 0; i <= n; i++) {
		int sum = 0;
		for (int j = i + 1; j <= n; j++) {
			sum += a[j];
			if (a[i] < sum && a[j + 1] < sum)
				dp[j + 1] = max(dp[j + 1], dp[i] + 2);
		}
	}
	return max(dp[n + 1] - 1, dp[n]);
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> l[i];
	cin >> q;
	for (int i = 1; i <= q; i++) {
		int x, y, aa, bb; cin >> x >> y >> aa >> bb; aa++;
		l[x] = y;
		for (int i = 1; i <= bb - aa + 1; i++)
			a[i] = l[i + aa - 1];
		n = bb - aa + 1;
		a[n + 1] = 0;
		cout << solve() << '\n';
	}
}

• Subtask 1: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 32
• Subtask 5: 0 / 29
• Subtask 6: 0 / 11