Pagini recente » Cod sursa (job #1294288) | Cod sursa (job #1709963) | Cod sursa (job #2158069) | Cod sursa (job #815867) | Cod sursa (job #3266566)
#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int main () {
ifstream f ("oo.in");
ofstream fout("oo.out");
int N;
f >> N;
// cout << "N = " << N << "\n";
vector<int> rates (N + 1, 0); // Fortran indexing
for (int i = 1; i < N + 1; i++) {
f >> rates[i];
}
// Check
// for (int i = 0; i < N; i++) {
// cout << rates[i] << "\n";
// }
vector<int> dp (N + 1, 0);
// Initially using cells 1 and 2 (Fortran indexing)
// dp(i) = the maximum # of eggs we can collect using the first ``i`` cells
// with the hard constraint that we mandatorily use cells 1 and 2
dp[0] = 0; // useless
dp[1] = 0;
dp[2] = rates[1] + rates[2];
dp[3] = dp[2];
dp[4] = dp[3];
for (int i = 5; i < N; i++) { // the last cell is forbidden to be used because we used cell 1
dp[i] = max(
dp[i - 1], // don't use this cell
rates[i] + rates[i - 1] + dp[i - 3] // use this cell
);
}
dp[N] = dp[N - 1];
int max_for_now = *max_element(dp.begin(), dp.end());
// cout << "max_for_now = " << max_for_now << " and dp[-1] = " << dp.back() << endl;
// Initially using cells 1 and N
fill(dp.begin(), dp.end(), 0); // reset
dp[0] = 0; // useless
dp[1] = rates[1] + rates[N];
dp[2] = dp[1];
dp[3] = dp[2];
for (int i = 4; i < N - 1; i++) { // the last cell has been already used, so cannot touch dp[N - 1]
dp[i] = max(
dp[i - 1], // don't take it
dp[i - 3] + rates[i] + rates[i - 1] // use this cell
);
}
dp[N - 1] = dp[N - 2];
dp[N] = dp[N - 1];
int max_for_now_2 = *max_element(dp.begin(), dp.end());
// cout << "max_for_now_2 = " << max_for_now_2 << " and dp[-1] = " << dp.back() << endl;
// Initially using cells 2 and 3
fill(dp.begin(), dp.end(), 0); // reset
dp[0] = 0;
dp[1] = 0;
dp[2] = 0;
dp[3] = rates[2] + rates[3];
dp[4] = dp[3];
dp[5] = dp[4];
for (int i = 6; i < N + 1; i++) {
dp[i] = max(
dp[i - 1],
dp[i - 3] + rates[i] + rates[i - 1]
);
}
int max_for_now_3 = *max_element(dp.begin(), dp.end());
// cout << "max_for_now_3 = " << max_for_now_3 << " and dp[-1] = " << dp.back() << endl;
fout << max({max_for_now, max_for_now_2, max_for_now_3}) << "\n";
return 0;
}