Submission #864270

#	Time	Username	Problem	Language	Result	Execution time	Memory
864270		serifefedartar	Cigle (COI21_cigle)	C++17	0 / 100	2 ms	2908 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 = 3005;

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

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

	A = vector<int>(N+1);
	for (int i = 1; i <= N; i++) {
		cin >> A[i];
		pref[i] = pref[i-1] + A[i];
	}

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

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

			if (balance == 0)
				now++;
			dp[l][r] = max(dp[l][r], dp[left_border][l-1] + now - (pref[r] - pref[l-1] == pref[l-1] - pref[left_border - 1]));
		}
	}

	cout << dp[N-1][N] << "\n";
}

Compilation message (stderr)

cigle.cpp: In function 'int main()':
cigle.cpp:31:29: warning: unused variable 'curr' [-Wunused-variable]
   31 |   int balance = 0, now = 0, curr = 0;
      |                             ^~~~

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