Pagini recente » Cod sursa (job #50244) | Cod sursa (job #1239119) | Cod sursa (job #1436964) | Cod sursa (job #1390216) | Cod sursa (job #1737082)
#include <fstream>
#define INF 10000005
#define DIM 100005
using namespace std;
ifstream f ("oo.in");
ofstream g ("oo.out");
int a1[DIM] , a2[DIM] , a3[DIM] , dp1[DIM][2] , dp2[DIM][2] , dp3[DIM][2];
int n;
int main() {
f >> n;
for (int i = 1; i <= n; ++i) {
f >> a1[i];
a2[i] = a1[i];
a3[i] = a2[i];
}
if (n == 2) {
g << a1[1] + a2[2];
return 0;
}
a2[1] = -INF;
a3[1] = -INF;
a3[2] = -INF;
for (int i = 2; i < n; ++i) {
dp1[i][0] = max(dp1[i - 1][0] , dp1[i - 1][1]);
dp1[i][1] = dp1[i - 2][0] + a1[i] + a1[i - 1];
dp2[i][0] = max(dp2[i - 1][0] , dp2[i - 1][1]);
dp2[i][1] = dp2[i - 2][0] + a2[i] + a2[i - 1];
dp3[i][0] = max(dp3[i - 1][0] , dp3[i - 1][1]);
dp3[i][1] = dp3[i - 2][0] + a3[i] + a3[i - 1];
}
dp1[n][0] = max(dp1[n - 1][0] , dp1[n - 1][1]);
dp1[n][1] = dp2[n - 2][0] + a1[n] + a1[n - 1];
dp1[n + 1][0] = max(dp1[n][0] , dp1[n][1]);
dp1[n + 1][1] = a1[n] + a1[1] + dp3[n - 1][0];
g << max (dp1[n + 1][0] , dp1[n + 1][1]);
return 0;
}