oj.uz

Submission #864270

# Submission time Handle Problem Language Result Execution time Memory
864270 2023-10-22T09:49:08 Z serifefedartar Cigle (COI21_cigle) C++17
0 / 100
 2 ms 2908 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 2 ms 2908 KB Output is correct
3 Correct 2 ms 2908 KB Output is correct
4 Incorrect 2 ms 2908 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -