Pagini recente » Cod sursa (job #1879287) | Cod sursa (job #2210907) | Cod sursa (job #2516229) | Cod sursa (job #2956926) | Cod sursa (job #2418242)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
const string FILE_NAME = "oo";
const int N_MAX { 100005 };
using Node = pair< int, pair<int, int> >;
ifstream in { FILE_NAME + ".in" };
ofstream out { FILE_NAME + ".out" };
int N;
vector<char> a(N_MAX);
vector<int> dp(N_MAX);
int sol;
void init() {
in >> N;
for (int i { 1 }; i <= N; ++i) {
int x;
in >> x;
a[i] = x;
}
}
void DP(int NMax) {
for (int i { 4 }; i <= NMax; ++i)
dp[i] = max(dp[i - 1], a[i] + a[i - 1] + dp[i - 3]);
}
void solve() {
// 1 si 2
dp[1] = 0;
dp[2] = a[1] + a[2];
dp[3] = dp[2];
DP(N - 1);
sol = dp[N - 1];
// 2 si 3
dp[1] = dp[2] = 0;
dp[3] = a[2] + a[3];
DP(N);
sol = max(sol, dp[N]);
// 1 si N
dp[1] = a[1] + a[N];
dp[2] = dp[3] = dp[1];
DP(N - 2);
sol = max(sol, dp[N - 2]);
}
void print() {
out << sol;
}
int main() {
init();
solve();
print();
}