Submission #1206806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206806		emptypringlescan	Mizuyokan 2 (JOI23_mizuyokan2)	C++17	0 / 100	2622 ms	4332 KiB

mizuyokan2

#include <bits/stdc++.h>
using namespace std;
int n,q;
long long arr[250005];
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i=1; i<=n; i++) cin >> arr[i];
	cin >> q;
	while(q--){
		int a;
		long long b;
		int c,d;
		cin >> a >> b >> c >> d;
		c++;
		arr[a]=b;
		long long dp[n+1];
		memset(dp,0,sizeof(dp));
		dp[1]=1;
		for(int i=2; i<=d-c+1; i++){
			long long sm=0;
			for(int j=i-1; j>0; j--){
				sm+=arr[c+j-1];
				if(sm<=arr[c+i-1]) continue;
				if(j>c&&arr[c+j-2]>=sm) continue;
				//cout << j << ' ' << i << ' ' << sm << ' ' << dp[j-1] << '\n';
				dp[i]=max(dp[i],dp[j-1]+2);
			}
			//cout << dp[i] << ' ';
		}
		long long ans=max(1ll,dp[d-c+1]),sm=0;
		for(int i=d-c; i>0; i--){
			sm+=arr[c+i];
			if(arr[c+i-1]<sm) ans=max(ans,dp[i]+1);
		}
		cout << ans << '\n';
	}
}

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