Submission #547531

#	Time	Username	Problem	Language	Result	Execution time	Memory
547531		penguinhacker	Cigle (COI21_cigle)	C++14	100 / 100	326 ms	67324 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], need[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=0; j<=i; ++j)
		//	cout << i << " " << j << " " << dp[i][j] << "\n";
		for (int j=i-1; ~j; --j)
			dp[i][j]=max(dp[i][j], dp[i][j+1]);
		vector<ar<int, 2>> oc;
		int ind=i, left=a[i];
		for (int j=i+1; j<n; ++j) {
			left-=a[j];
			while(ind>0&&left<0)
				left+=a[--ind];
			if (ind>0&&left==0) {
				left+=a[--ind];
				oc.push_back({j+1, i-ind});
			}
		}
		int cur=dp[i][0];
		for (int j=i+1, k=0; j<n; ++j) {
			if (k<oc.size()&&oc[k][0]==j) {
				cur=max(cur, dp[i][oc[k][1]]+k+1);
				++k;
			}
			dp[j][j-i-1]=max(dp[j][j-i-1], cur);
		}
	}
	cout << *max_element(dp[n-1], dp[n-1]+n);
	return 0;
}

Compilation message (stderr)

cigle.cpp: In function 'int main()':
cigle.cpp:34:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |    if (k<oc.size()&&oc[k][0]==j) {
      |        ~^~~~~~~~~~

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