Submission #547448

#	Time	Username	Problem	Language	Result	Execution time	Memory
547448		penguinhacker	Cigle (COI21_cigle)	C++14	48 / 100	1085 ms	24856 KiB

cigle

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

#define ll long long
#define ar array

const int mxN=5000;
int n, a[mxN], dp[mxN][mxN];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i=0; i<n; ++i)
		cin >> a[i];
	for (int i=0; i<n; ++i) {
		for (int j=i-1; ~j; --j)
			dp[i][j]=max(dp[i][j], dp[i][j+1]);
		for (int j=0; j<=i; ++j) { // current seg [i-j, i] -> [i+1, something]
			int cur=dp[i][j], ind=i, left=a[i];
			for (int k=i+1; k<n; ++k) {
				left-=a[k];
				while(ind>i-j&&left<=0) {
					cur+=left==0;
					left+=a[--ind];
				}
				dp[k][k-i-1]=max(dp[k][k-i-1], cur-(left==a[ind]));
			}
			//cout << i << " " << j << " " << dp[i][j] << endl;
		}
	}
	cout << *max_element(dp[n-1], dp[n-1]+n);
	return 0;
}

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