Pagini recente » Cod sursa (job #770737) | Cod sursa (job #314857) | Monitorul de evaluare | Cod sursa (job #794530) | Cod sursa (job #2705056)
//
// main.cpp
// oo
//
// Created by Eusebiu Rares on 11.02.2021.
//
#include <iostream>
#include <fstream>
#include <vector>
#pragma GCC ("O3")
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
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, s ;
int main(int argc, const char * argv[]) {
int n ;
in >> n ;
v.resize(n + 1) ;
dp.resize(n + 1) ;
s.resize(n + 1) ;
in >> v[0] ;
for (register int i = 1 ; i < n ; ++ i) {
in >> v[i] ;
s[i] = v[i - 1] + v[i] ;
}
v[n] = v[0] ;
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] = MAX(dp[i - 1], dp[i - 3] + s[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] = MAX(dp[i - 1], dp[i - 3] + s[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] = MAX(dp[i - 1], dp[i - 3] + s[i]) ;
}
int third(dp[right]) ;
out << MAX(first, MAX(second, third));
}