Submission #420474

#	Time	Username	Problem	Language	Result	Execution time	Memory
420474		Pyqe	Cigle (COI21_cigle)	C++14	100 / 100	540 ms	235308 KiB

cigle

#include <bits/stdc++.h>

using namespace std;

const long long inf=1e18;
long long n,ps[5069],px[2][5069][5069],fh[5069],fq[5069];

int main()
{
	long long i,j,k,z=0;
	
	scanf("%lld",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%lld",ps+i);
		ps[i]+=ps[i-1];
	}
	for(i=1;i<=n;i++)
	{
		px[0][i][0]=-inf;
		px[0][i][1]=-inf;
		px[1][i][1]=-inf;
		for(j=0;j<i;j++)
		{
			k=max(px[0][j][fh[j]]+fq[j],px[1][j][fh[j]+1]);
			z=max(z,k);
			px[0][i][j+2]=max(px[0][i][j+1],k);
			px[1][i][j+2]=k;
			for(;fh[j]&&ps[j]-ps[fh[j]-1]<=ps[i]-ps[j];fh[j]--)
			{
				fq[j]+=ps[j]-ps[fh[j]-1]==ps[i]-ps[j];
				px[1][j][fh[j]]=max(px[1][j][fh[j]+1],px[1][j][fh[j]]+fq[j]);
			}
		}
		px[1][i][i+2]=-inf;
		fh[i]=i+1;
	}
	printf("%lld\n",z);
}

Compilation message (stderr)

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

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