PROG-1150: Pangpu

#include <bits/stdc++.h>

using namespace std;

int n;
int hole[1005];
bool dp[2][60005];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&hole[i]);
    dp[0][30000] = true;
    for(int k=1;k<=n;k++){
        for(int j=-30000;j<=30000;j++){
            int s = j - hole[k];
            if(s < -30000)
                s += 60001;
            else if(s > 30000)
                s -= 60001;
            dp[k%2][j+30000] = dp[(k+1)%2][s+30000] or dp[(k+1)%2][j+30000];
        }
    }
    for(int i=60000;i>=0;i--){
        if(dp[n%2][i]){
            printf("%d ",i-30000);
            break;
        }
    }
}