Cod sursa(job #2705044)

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

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

template <typename T>
class InputReader {
private:
	FILE *input_file ;
	static const int SIZE = (1 << 17) ;
	int point ;
	char buffer[SIZE] ;
	__attribute__ ( (always_inline)) void advance() {
		++ point ;
		if (point == SIZE) {
			point = 0 ;
			fread (buffer, SIZE, 1, input_file) ;
		}
	}
public:
	InputReader() {}
	InputReader (const char *file_name) {
		input_file = fopen (file_name, "r") ;
		point = 0 ;
		fread (buffer, SIZE, 1, input_file) ;
	}
	__attribute__ ( (always_inline)) InputReader &operator >> (T &n) {
		for (; !isdigit (buffer[point]) ; advance()) ;
		n = 0 ;
		for (; isdigit (buffer[point]) ; advance()) {
			n = n * 10 + buffer[point] - '0' ;
		}
		return *this ;
	}
} ;

InputReader<int> in ("oo.in") ;

class OutoutParsing {
public:
	OutoutParsing() {} ;
	
	OutoutParsing(const char * file_name) {
		output_file.open(file_name, std::ios::out | std::ios::binary) ;
		output_file.sync_with_stdio(false) ;
		index = 0 ;
	}
	
	inline OutoutParsing & operator << (int target) {
		aux = 0 ;
		n = target ;
		target < 0 ? sign = -1 : sign = 1 ;
		if (!n) {
			nr[aux ++] = '0' ;
		}
		for ( ; n ; n /= 10) {
			nr[aux ++] = sign * (n % 10) + '0' ;
		}
		if (sign == -1) {
			buffer[index] = '-' ;
			inc() ;
		}
		for ( ; aux ; inc())
		buffer[index] = nr[-- aux] ;
		return *this ;
	}
	
	inline OutoutParsing & operator << (const char * target) {
		aux = 0 ;
		while (target[aux]) {
			buffer[index] = target[aux ++] ;
			inc() ;
		}
		return *this ;
	}
	~OutoutParsing() {
		output_file.write(buffer, index) ;
		output_file.close() ;
	}
	
private:
	std::fstream output_file;
	static const int SIZE = 0x200000;
	int index = 0, aux, n, sign;
	char buffer[SIZE], nr[24];
	
	inline void inc() {
		if (++index == SIZE) {
			index = 0 ;
			output_file.write(buffer, SIZE);
		}
	}
} out ("oo.out") ;

std::vector<int> v ;

const int maxn = 1e5 ;

int dp1[1 + maxn][4] ;

int solve(int n) {
	dp1[0][1] = 0 ;
	dp1[1][1] = v[0] + v[1] ;
	
	dp1[1][2] = 0 ;
	dp1[2][2] = v[1] + v[2] ;
	
	dp1[2][3] = 0 ;
	dp1[3][3] = v[2] + v[3] ;
	
	for (int i = 2 ; i <= n - 2 ; ++ i) {
		dp1[i][1] = std::max(dp1[i - 1][1], dp1[i - 3][1] + v[i - 1] + v[i]) ;
		dp1[i + 1][2] = std::max(dp1[i][2], dp1[i - 2][2] + v[i] + v[i + 1]) ;
		dp1[i + 2][3] = std::max(dp1[i + 1][3], dp1[i - 1][3] + v[i + 1] + v[i + 1]) ;
	}
	
	return std::max(dp1[n - 2][1], std::max(dp1[n - 1][2], dp1[n][3]));
}

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