Submission #1246391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246391		45dino	Cigle (COI21_cigle)	C++20	0 / 100	2 ms	2884 KiB

cigle

#include<bits/stdc++.h>
#define ll long long
#define elif else if
#define lowbit(x) (x&(-(x)))
#define ALL(x) x.begin(),x.end()
using namespace std;
void fileio(const string &s)
{
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}
const ll INF=4e18;
ll read()
{
	ll x=0;
	bool flag=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
			flag=0;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return (flag?x:~(x-1));
}
int n,ans,a[5010],f[5010][5010];
int main()
{
	// fileio("C");
	n=read();
	for(int i=1;i<=n;i++)
		a[i]=read(),a[i]+=a[i-1];
	for(int i=1;i<=n;i++)
	{
		int x=i+1,cnt=0,ad=0;
		for(int l=1;l<=i;l++)
			f[i][l]=max(f[i][l],f[i-1][l]);
		// for(int l=1;l<=i;l++)
			// cout<<f[i][l]<<" ";
		// cout<<'\n';
		for(int l=1;l<=i;l++)
			f[i][l]=max(f[i][l],f[i][l-1]);
		
		for(int l=i-1;~l;l--)
		{
			while(x<=n&&a[x]-a[i]<=a[i]-a[l])
			{
				// cout<<l<<" "<<i<<" "<<x<<" "<<cnt<<'\n';
				f[x][i+1]=max(f[x][i+1],f[i][l+1]+cnt);
				if(a[x]-a[i]==a[i]-a[l])
					cnt++;
				x++;
			}
		}
		while(x<=n)
			f[x][i+1]=max(f[x][i+1],f[i][1]+cnt),x++;
	}
	cout<<f[n][n];
	return 0;
}

Compilation message (stderr)

cigle.cpp: In function 'void fileio(const string&)':
cigle.cpp:9:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |         freopen((s+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cigle.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen((s+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 52