Submission #854950

#	Time	Username	Problem	Language	Result	Execution time	Memory
854950		QuangBui	Cigle (COI21_cigle)	C++14	100 / 100	87 ms	97532 KiB

cigle

// QuangBuiCP
#ifndef LOCAL
#pragma GCC optimize(3)
#pragma GCC target("avx2")
#endif // LOCAL
#include "bits/stdc++.h"
using namespace std;

#define SZ(a) (int)(a).size()
#define ALL(a) (a).begin(),(a).end()

const int N = 5005;

int n;
int a[N];
int pref[N];
int dp[N][N];
int f[N];

int Brute() {
	int ret = 0;
	for (int mask = 0; mask < (1 << n); ++mask) {
		int cnt = 0;
		set<int> prv, cur;
		int pos = 0, layer = 0;
		bool no = false;
		for (int i = 1; i < n; ++i) {
			int x1 = 0, x2 = 0;
			if (mask >> i & 1) {
				x1 = 1;
			}
			if (mask >> (i - 1) & 1) {
				x2 = 1;
			}
			if (x1 && x2) {
				no = true;
				break;
			}
		}
		if (no) {
			continue;
		}
		for (int i = 0; i < n; ++i) {
			if (mask >> i & 1) {
				layer++;
				prv = cur;
				cur.clear();
			}
			int sign = 1;
			if (layer % 2) {
				sign *= -1;
			}
			pos += sign * a[i + 1];
			if (prv.count(pos) && i != n - 1 && !(mask >> (i + 1) & 1)) {
				cnt++;
			}
			cur.insert(pos);
		}
		ret = max(ret, cnt);
	}
	return ret;
}

signed main() {
#ifndef LOCAL
	cin.tie(nullptr)->sync_with_stdio(false);
#endif // LOCAL

	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		a[i] += a[i - 1];
	}
	// cout << Brute() << '\n';
	for (int j = 1; j <= n; ++j) {
		for (int i = 0; i < j; ++i) {
			f[i] = dp[i][j];
		}
		for (int i = 1; i < j; ++i) {
			f[i] = max(f[i], f[i - 1]);
		}
		int cur = 0, cnt = 0;
		for (int i = j - 1, k = j + 1; k <= n; ++k) {
			dp[j][k] = cur;
			while (i > 0 && a[i] + a[k] > a[j] * 2) {
				i--;
			}
			if (i > 0 && a[i] + a[k] == a[j] * 2) {
				cnt++;
				cur = max(cur, f[i - 1] + cnt);
			}
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		ans = max(ans, dp[i][n]);
	}
	cout << ans << '\n';

#ifdef LOCAL
	cerr << '\n' << clock() << "ms.";
#endif // LOCAL
	return 0;
}

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