Submission #290435

#	Time	Username	Problem	Language	Result	Execution time	Memory
290435		luciocf	Bigger segments (IZhO19_segments)	C++14	13 / 100	2 ms	640 KiB

segments

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef long long ll;

const int maxn = 5e5+10;
const ll inf = 1e18+10;

ll v[maxn];

struct SegmentTree
{
	ll tree[4*maxn];

	void build(int node, int l, int r)
	{
		if (l == r)
		{
			tree[node] = v[l];
			return;
		}

		int mid = (l+r)>>1;

		build(2*node, l, mid); build(2*node+1, mid+1, r);

		tree[node] = min(tree[2*node], tree[2*node+1]);
	}

	int query(int node, int l, int r, int pos, ll v)
	{
		if (l > pos || tree[node] > v) return -1;
		if (l == r) return l;

		int mid = (l+r)>>1;

		int p1 = query(2*node+1, mid+1, r, pos, v);

		if (p1 == -1) return query(2*node, l, mid, pos, v);
		return p1;
	}
} seg;

int a[maxn];

ll pref[maxn];

ll dp[maxn][55];

int main(void)
{
	int n;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);

	for (int i = 1; i <= n; i++)
		for (int j = 2; j < 55; j++)
			dp[i][j] = inf;

	for (int i = 1; i <= n; i++)
	{
		pref[i] = pref[i-1] + 1ll*a[i];
		dp[i][1] = pref[i];

		v[i] = dp[i][1]+pref[i];
	}

	for (int j = 2; j < 55; j++)
	{
		seg.build(1, 1, n);

		for (int i = j; i <= n; i++)
		{
			int p = seg.query(1, 1, n, i-1, pref[i]);

			if (p != -1) dp[i][j] = pref[i]-pref[p];
		}

		for (int i = 1; i <= n; i++)
			v[i] = min(inf, dp[i][j]+pref[i]);
	}

	int ans = 1;
	for (int i = 1; i < 55; i++)
		if (dp[n][i] != inf)
			ans = i;

	printf("%d\n", ans);
}

Compilation message (stderr)

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

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