Cod sursa(job #2705053)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 11 februarie 2021 20:22:16
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.04 kb
	//
	//  main.cpp
	//  oo
	//
	//  Created by Eusebiu Rares on 11.02.2021.
	//
	 
	#include <iostream>
	#include <fstream>
	#include <vector>

#pragma GCC ("O3")
	 
	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, dp ;
	
	inline int solve(int n) {
		int left(0), right(n - 2) ;
		dp[left] = 0 ;
		dp[left + 1] = v[left] + v[left + 1] ;
		for (register int i = left + 2 ; i <= right ; ++ i) {
			dp[i] = std::max(dp[i - 1], dp[i - 3] + v[i - 1] + v[i]) ;
		}
		int first(dp[right]) ;
		left = 1 ; right = n - 1 ;
		dp[left] = 0 ;
		dp[left + 1] = v[left] + v[left + 1] ;
		for (register int i = left + 2 ; i <= right ; ++ i) {
			dp[i] = std::max(dp[i - 1], dp[i - 3] + v[i - 1] + v[i]) ;
		}
		int second(dp[right]) ;
		left = 2 ; right = n ;
		dp[left] = 0 ;
		dp[left + 1] = v[left] + v[left + 1] ;
		for (register int i = left + 2 ; i <= right ; ++ i) {
			dp[i] = std::max(dp[i - 1], dp[i - 3] + v[i - 1] + v[i]) ;
		}
		int third(dp[right]) ;
		return std::max(first, std::max(second, third));
	}
	 
	int main(int argc, const char * argv[]) {
		int n ;
		in >> n ;
		v.resize(n + 1) ;
		dp.resize(n + 1) ;
		for (register int i = 0 ; i < n ; ++ i) {
			in >> v[i] ;
		}
		v[n] = v[0] ;
		int ans(solve(n)) ;
		out << ans ;
	}