Pagini recente » Profil AlexMari | Cod sursa (job #3356593)
#include <fstream>
#include <vector>
#define MAX 100005
using namespace std;
ifstream fin ("oo.in");
ofstream fout ("oo.out");
int v[MAX];
int solve(int st, int dr) {
if (st>dr) {
return 0;
}
if (st==dr) {
return 0;
}
vector<int> dp(dr+1, 0);
for (int i=st; i<=dr; i++) {
if (i>st) {
dp[i]=dp[i-1];
}
if (i-1>=st) {
int prec,val=v[i-1]+v[i];
if (i-3>=st) {
prec=dp[i-3];
} else {
prec=0;
}
dp[i]=max(dp[i], prec+val);
}
}
return dp[dr];
}
int main() {
int n,i;
fin>>n;
for (i=1; i<=n; i++) {
fin>>v[i];
}
int ans1=v[1]+v[2]+solve(4, n-1);
int ans2=v[2]+v[3]+solve(5, n);
int ans3=v[n]+v[1]+solve(3, n-2);
int ans4=solve(2, n);
int maxim=max(max(ans1, ans2), max(ans3, ans4));
fout<<maxim<<endl;
return 0;
}