Submission #290442

#	Time	Username	Problem	Language	Result	Execution time	Memory
290442		luciocf	Bigger segments (IZhO19_segments)	C++14	37 / 100	709 ms	71344 KiB

segments

#include <bits/stdc++.h>
 
#define ff first
#define ss second
 
using namespace std;
 
typedef long long ll;
 
const int maxn = 3e3+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][maxn];
 
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 <= n; 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 <= n; 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 <= n; 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: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27