1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define LEFT 1
#define RIGHT 2
#define EMPTY 0

int stackp, all, rest, Left, Right, btd, Max, n;


bool check_improve() {
    return Left+Right+rest > Max && rest >= max(Left-Right, Right-Left);
}

void check_current() {
    if(Left==Right && (Left+Right) > Max) Max=Left+Right; 
}

void bt(){
    //cout << "bt: stackp="<< stackp << endl;
    btd = 1;
}

bool is_bt(){
    return btd==1;
}

void advance(vector<int>& state) {
    stackp++;
    if(stackp<n)
        state[stackp]=(stackp%2)?LEFT:RIGHT;
}

void make_Left(vector<int>& v, vector<int>& state){
    Left+=v[stackp];
    rest-=v[stackp];
    check_current();
    if(check_improve())
        advance(state);
    else 
        bt();
}

void make_Right(vector<int>& v, vector<int>& state){
    Right+=v[stackp];
    rest-=v[stackp];
    check_current();
    if(check_improve())
        advance(state);
    else 
        bt();
}

void make_empty(vector<int>& v, vector<int>& state){
    rest-=v[stackp];
    if(check_improve())
        advance(state);
    else 
        bt();
}


void make_bt(vector<int>& v, vector<int>& state){
    if (stackp == n) stackp-1;
    int ind = stackp%2;
    rest+=v[stackp];
    if(state[stackp]==RIGHT){ Right-=v[stackp]; }
    if(state[stackp]==LEFT){ Left-=v[stackp]; }
    if(ind==1&&state[stackp]==EMPTY || ind==0&&state[stackp]==LEFT){
        stackp--;
    } else {
        state[stackp] = (state[stackp]+1)%3;
        btd=0;
    }
}



int main(){
    cin>>n;
    vector<int> v(n);
    vector<int> states(n);
    fill(states.begin(), states.end(),LEFT);
    for(int i = 0; i < n; i++){cin>>v[i];}
    
    stackp = 0;
    states[0] = RIGHT;
    all = 0;
    for(int i = 0; i < n; i++){all+=v[i];}
    rest = all;
    Left = 0;
    Right = 0;
    btd = 0;
    Max = 0;
    
    while(stackp!=0||states[0]!=LEFT){
        if(stackp==n){bt();}
        if(is_bt()) {make_bt(v, states); continue;}
        if(states[stackp]==LEFT) {make_Left(v, states); continue;}
        if(states[stackp]==RIGHT) {make_Right(v, states); continue;}
        if(states[stackp]==EMPTY) {make_empty(v, states); continue;}
    }
    if(Max==0) cout << "NIESTETY"; else cout<<Max;
    return 0;
}