Submission #1295057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295057		danirasilla	Cigle (COI21_cigle)	C++20	100 / 100	292 ms	98540 KiB

cigle

#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <iterator>
#include <set>
#include <random>
#include <unordered_map>
#include <queue>
#include <cassert>
#include <stack>
#include <numeric>
#include <deque>


using namespace std;
typedef long long ll;
typedef long double ld;
const ll md1 = 1'000'000'007;
const ll md2 = 998244353;
const ll mdd = 666013;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int t = 1;
	//cin >> t;
	while (t--) {
		
		int n;
		cin >> n;
		vector<int> d(n), p(n + 1);
		for (int i = 0; i < n; i++) {
			cin >> d[i];
			p[i + 1] = p[i] + d[i];
		}
		vector<vector<int>> dp(n, vector<int>(n + 1));
		for (int l = 1; l < n; l++) {
			dp[l][l] = dp[l-1][l];
			dp[l][l + 1] = dp[l][l];
			int k = l - 1;
			int cnt = 0;
			for (int r = l + 2; r <= n; r++) {
				while (k > 0 && p[r - 1] - p[l] > p[l] - p[k])
					k--;
				if (p[r - 1] - p[l] == p[l] - p[k] && k > 0) {
					cnt++;
					k--;
				}
				dp[l][r] = max(dp[l][r - 1], dp[k][l] + cnt);
			}
			for (int i = 1; i < n; i++)
				dp[i][l + 1] = max(dp[i - 1][l + 1], dp[i][l + 1]);
		}
		cout << dp[n - 1][n] << "\n";
	}
	return 0;
}

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