Cod sursa(job #2673174)

Utilizator popoviciAna16Popovici Ana popoviciAna16 Data 16 noiembrie 2020 09:28:03
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <fstream>
using namespace std;

ifstream fin("oo.in");
ofstream fout("oo.out");

int a[100001];
long long dp[100001]; //dp[i] = nr. maxim de oua pentru [1...i] (aprox.)

long long dpf(int st, int dr)
{
	int i;
	for (i = st; i<=dr; i++)
		dp[i] = max(dp[i-1], dp[i-3] + a[i] + a[i-1]);
	if (st > dr)
		return 0;
	return dp[dr];
}

int main()
{
	int n, i;
	long long rasp;
	fin >> n;
	for (i = 1; i<=n; i++)
		fin >> a[i];
	
	rasp = dpf(3, n);
	
	dp[1] = dp[2] = dp[3] = a[1] + a[n];
	rasp = max(rasp, dpf(4, n-2));
	
	dp[1] = 0;
	dp[2] = dp[3] = dp[4] = a[1] + a[2];
	rasp = max(rasp, dpf(5, n-1));
	
	fout << rasp;
	return 0;
}