Submission #434926

#	Time	Username	Problem	Language	Result	Execution time	Memory
434926		dqhungdl	Cigle (COI21_cigle)	C++17	100 / 100	365 ms	178884 KiB

cigle

#include <bits/stdc++.h>
using namespace std;

const int MAX=5005;
int N,S[MAX],mark[MAX][MAX],f[MAX][MAX],maxf[MAX][MAX];

int main() {
#ifdef ACM
	freopen("input","r",stdin);
#endif
	cin>>N;
	for(int i=1;i<=N;i++) {
		cin>>S[i];
		S[i]+=S[i-1];
	}
	for(int i=1;i<=N;i++) {
		int cur=i;
		for(int j=i+1;j<=N;j++) {
			while(cur>0&&S[i]-S[cur-1]<S[j]-S[i])
				cur--;
			if(cur>0&&S[i]-S[cur-1]==S[j]-S[i])
				mark[i][j]=cur;
		}
	}
	for(int i=0;i<N;i++) {
		int cnt=0,maxVal=maxf[i][i-1];
		for(int j=i+1;j<=N;j++) {
			f[i][j]=maxVal;
			if(mark[i][j]>1) {
				cnt++;
				maxVal=max(maxVal,maxf[i][mark[i][j]-2]+cnt);
			}
		}
		for(int j=i+1;j<=N;j++)
			maxf[j][i]=max(maxf[j][i-1],f[i][j]);
	}
	int rs=0;
	for(int i=0;i<N;i++)
		rs=max(rs,f[i][N]);
	cout<<rs;
}

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