Submission #434922

#	Time	Username	Problem	Language	Result	Execution time	Memory
434922		dqhungdl	Cigle (COI21_cigle)	C++17	48 / 100	1093 ms	68868 KiB

cigle

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

const int MAX=5005;
int N,S[MAX],mark[MAX][MAX],f[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=1;i<=N;i++)
		for(int j=0;j<i;j++) {
			int cnt=0;
			for(int t=j+1;t<=N;t++) {
				f[t][i]=max(f[t][i],f[i][j]+cnt);
				cnt+=(mark[i][t]>j+1);
			}
		}
	int rs=0;
	for(int i=1;i<N;i++)
		rs=max(rs,f[N][i]);
	cout<<rs;
}

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