PROG-1150: Pangpu

#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
int change(int i){
    if(i<-30000) return i+60001;
    if(i> 30000) return i-60001;
    return i;
}
bool dp1[60001],dp2[60001];
int main(){

    int n,mx=0;
    scanf("%d",&n);
    int ar[n+1];
    for(int i=1;i<=n;i++) scanf("%d",&ar[i]);

    dp1[30000]=true;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=60000;j++){
            if(i%2==1) {
                dp2[j] = dp1[j] or dp1[change(j-ar[i]-30000)+30000];
                if(dp2[j]) mx=max(mx,j-30000);
            }
            else {
                dp1[j] = dp2[j] or dp2[change(j-ar[i]-30000)+30000];
                if(dp1[j]) mx=max(mx,j-30000);
            }
        }
    }
    printf("%d",mx);


    return 0;
}