#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; }
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; } |