Submission #376316

#	Time	Username	Problem	Language	Result	Execution time	Memory
376316		jamezzz	Bigger segments (IZhO19_segments)	C++14	27 / 100	1583 ms	35820 KiB

segments

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

typedef tree<long long, null_type, less<long long>,
rb_tree_tag, tree_order_statistics_node_update> pbds;
//less_equal for identical elements

#define DEBUG

#ifdef DEBUG
#define debug(...) printf(__VA_ARGS__);
#else
#define debug(...)
#endif
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;

int n,a[500005],memo[3005][3005];
ll pfx[500005];

int dp(int x,int y){
	//current segment covers (x, y]
	if(memo[x][y]!=-1)return memo[x][y];
	int ans=0;
	for(int i=y+1;i<=n;++i){
		if(pfx[i]-pfx[y]>=pfx[y]-pfx[x]){
			ans=max(ans,dp(y,i)+1);
		}
	}
	return memo[x][y]=ans;
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		pfx[i]=pfx[i-1]+a[i];
	}
	memset(memo,-1,sizeof memo);
	printf("%d\n",dp(0,0));
}

Compilation message (stderr)

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

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