제출 #864286

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
864286		serifefedartar	Cigle (COI21_cigle)	C++17	100 / 100	137 ms	79248 KiB

cigle

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 20; 
const ll MAXN = 5005;

vector<int> A;
int dp[MAXN][MAXN];

int main() {
	fast
	int N;
	cin >> N;

	A = vector<int>(N);
	for (int i = 0; i < N; i++)
		cin >> A[i];

	for (int l = 0; l <= N; l++) {
		for (int l2 = 1; l2 < l; l2++)
			dp[l2][l] = max(dp[l2][l], dp[l2-1][l]);

		int bal = 0, match = 0, curr = 0, left_border = l;
		for (int r = l+1; r <= N; r++) {
			bal += A[r-1];
			while (left_border > 0 && bal - A[left_border - 1] >= 0) {
				bal -= A[left_border - 1];
				left_border--;
			}

			dp[l][r] = max(dp[l][r-1], curr);

			if (bal == 0) {
				match++;
				if (left_border) 
					curr = max(curr, dp[left_border - 1][l] + match);
			}
		}
	}
	cout << dp[N-1][N] << "\n";
}

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