Submission #1308385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308385		thuhienne	Mizuyokan 2 (JOI23_mizuyokan2)	C++20	15 / 100	4091 ms	2756 KiB

mizuyokan2

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define re exit(0);

int n,d[250009];

int dp[250009];
ll pref[250009];

int calc(vector <int> & arr) {
	
	arr.insert(arr.begin(),0);
	arr.push_back(0);
	
	int n = (int)arr.size() - 1;
	
	for (int i = 1;i <= n;i++) pref[i] = pref[i - 1] + arr[i];

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

void solve() {
	int x,y,a,b;cin >> x >> y >> a >> b;
	d[x] = y;
	
	vector <int> temp;
	for (int i = a + 1;i <= b;i++) temp.push_back(d[i]);
	
	cout << calc(temp) << '\n';
	
}

int main() {
  ios_base::sync_with_stdio(0);cin.tie(nullptr);

	cin >> n;
	for (int i = 1;i <= n;i++) cin >> d[i];
	
	int q;cin >> q;while (q--) solve();

}

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