Cod sursa(job #3146442)

Utilizator AztecaVlad Tutunaru 2 Azteca Data 21 august 2023 02:01:35
Problema Oo Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = (int) 1e5 + 7;
int n;
int a[N], dp[N];

int solve(int first) {
  dp[first - 1] = 0;
  dp[first] = 0;
  dp[first + 1] = a[first] + a[first + 1];
  for (int i = first + 2; i <= n + 1; i++) {
    dp[i] = max(dp[i - 1], dp[i - 3] + a[i - 1] + a[i]);
  }
  return dp[n - 2 + first];
}

signed main() {
#ifdef ONPC
  freopen ("input.txt", "r", stdin);
#else
  ios::sync_with_stdio(0); cin.tie(0);
  freopen ("oo.in", "r", stdin);
  freopen ("oo.out", "w", stdout);
#endif // ONPC

  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  a[n + 1] = a[n];
  int sol = -1;
  for (int i = 1; i <= 3; i++) {
    sol = max(sol, solve(i));
  }
  cout << sol << "\n";
  return 0;
}