Cod sursa(job #2705035)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 11 februarie 2021 20:03:34
Problema Oo Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
//
//  main.cpp
//  oo
//
//  Created by Eusebiu Rares on 11.02.2021.
//

#include <iostream>
#include <fstream>
#include <vector>

std::fstream in ("oo.in", std::ios::in) ;
std::fstream out ("oo.out", std::ios::out) ;

int solve(int left, int right, std::vector<int> v) {
	std::vector<int> dp(right + 1) ;
	dp[left] = 0 ;
	dp[left + 1] = v[left] + v[left + 1] ;
	for (int i = left + 2 ; i <= right ; ++ i) {
		dp[i] = std::max(dp[i - 1], dp[i - 3] + v[i - 1] + v[i]) ;
	}
	return dp[right] ;
}

int solve(std::vector<int> v, int n) {
	int first(solve(0, n - 2, v)) ;
	int second(solve(1, n - 1, v)) ;
	int third(solve(2, n, v)) ;
	return std::max(first, std::max(second, third));
}

int main(int argc, const char * argv[]) {
	int n, x ;
	in >> n ;
	std::vector<int> v(n + 1) ;
	for (int i = 0 ; i < n ; ++ i) {
		in >> v[i] ;
	}
	v[n] = v[1] ;
	int ans(solve(v, n)) ;
	out << ans ;
}