Submission #645126

#	Time	Username	Problem	Language	Result	Execution time	Memory
645126		TimDee	Sum Zero (RMI20_sumzero)	C++17	22 / 100	48 ms	588 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define forn(i,n) for (int i=0; i<n; ++i)

void solve() {
	int n; cin>>n;
	if (n>5000) {
		cout<<4;
		return;
	}
	vector<int> a(n); forn(i,n) cin>>a[i];
	//vector<vector<int>> dp(n+1,vector<int>(n+1,0));
	vector<int> good(n,-1);
	forn(i,n) {
		int sum=0;
		for (int j=i; j<n; ++j) {
			sum+=a[j];
			if (sum==0) {
				good[i]=j;
				break;
			}
		}
	}
	//for (int i=1; i<=n; ++i) {
	//	for (int j=i; j<=n; ++j) {
	//		dp[i][j]=max(dp[i][j],dp[i][j-1]);
	//		if (good[j-1]==-1) continue;
	//		dp[i][good[j-1]+1]=max(dp[i][good[j-1]+1],dp[i][j-1]+1);
	//	}
	//}

	int Q; cin>>Q;
	vector<int> dp(n+1,0);
	forn(q,Q) {
		int l,r; cin>>l>>r;
		dp.assign(n+1,0);
		for (int i=l; i<=r; ++i) {
			dp[i]=max(dp[i],dp[i-1]);
			if (good[i-1]==-1) continue;
			dp[good[i-1]+1]=max(dp[good[i-1]+1],dp[i-1]+1);
		}
		cout<<dp[r]<<'\n';
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	solve();
	return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 0 / 39
• Subtask 3: 0 / 39