Submission #290793

#	Time	Username	Problem	Language	Result	Execution time	Memory
290793		PeppaPig	Bigger segments (IZhO19_segments)	C++14	0 / 100	1 ms	384 KiB

segments

#include <bits/stdc++.h>

#define long long long
#define pii pair<long, long>
#define x first
#define y second

using namespace std;

const int N = 5e5 + 5;

int n, dp[N];
long A[N], pref[N];

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%lld", A + i);
		pref[i] = pref[i - 1] + A[i];
	}
	
	vector<pii> vec;
	int ans = 0;
	vec.emplace_back(0, 0);
	for(int i = 1; i <= n; i++) {
		int idx = -1;
		long val = -1;
		for(pii p : vec) if(p.x <= pref[i] && p.x > val)
			val = p.x, idx = p.y;
		dp[i] = dp[idx] + 1, vec.emplace_back(2ll * pref[i] - pref[idx], i);
		ans = max(ans, dp[i]);
	}
	printf("%d\n", ans);

	return 0;

}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   16 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
segments.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |   scanf("%lld", A + i);
      |   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27