Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define F first
- #define S second
- //#define mp make_pair
- #define pb push_back
- #define loop(i,x,y) for(int i=x;i<=y;i++)
- using namespace std;
- typedef long long ll;
- const int N = 5e3 + 9;
- const int MOD = 1e9 + 7;
- const int INF = 1e9 + 1;
- int prefixSum[N], dp[N][N], A[N], prevOdd[N], nextOdd[N], segTree[2][N][4*N];
- int main () {
- int n, firstOdd = -1, lastOdd = -1;
- cin >> n;
- for (int i = 1; i <= n; i++) {
- cin >> A[i];
- prefixSum[i] = prefixSum[i - 1] + A[i];
- }
- int last = 0;
- for (int i = 1; i <= n; i++) {
- if (last)
- prevOdd[i] = last;
- else prevOdd[i] = 0;
- if (A[i] & 1) {
- last = i;
- if (firstOdd == -1)
- firstOdd = i;
- }
- }
- last = 0;
- for (int i = n; i >= 1; i--) {
- if (last)
- nextOdd[i] = last;
- else nextOdd[i] = n + 1;
- if (A[i] & 1) {
- last = i;
- if (lastOdd == -1)
- lastOdd = i;
- }
- }
- dp[1][n] = prefixSum[n];
- for (int len = n - 1; len >= 1; len--) {
- for (int l = 1; l + len - 1 <= n; l++) {
- int r = l + len - 1;
- if (r >= lastOdd && l <= firstOdd) {
- dp[l][r] = prefixSum[r] - prefixSum[l - 1];
- continue;
- }
- int bestBelowFloor = -INF;
- if (r < lastOdd) {
- for (int k = nextOdd[r]; k <= nextOdd[nextOdd[r]] - 1; k++)
- bestBelowFloor = max (bestBelowFloor, dp[l][k]);
- }
- if (l > firstOdd) {
- for (int k = prevOdd[prevOdd[l]] + 1; k <= prevOdd[l]; k++)
- bestBelowFloor = max (bestBelowFloor, dp[k][r]);
- }
- dp[l][r] = prefixSum[r] - prefixSum[l - 1] + bestBelowFloor;
- }
- }
- int res = -INF;
- for (int l = 1; l <= n; l++) {
- int c = 0;
- for (int r = l; r <= n; r++) {
- if (A[r] & 1)
- c++;
- if (((prefixSum[r] - prefixSum[l - 1]) & 1) && c == 1)
- res = max (res, dp[l][r]);
- }
- }
- if (res == -INF)
- cout << -1 << "\n";
- else cout << res << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment