水个差值DP

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2000; 
bool dp[2][MAXN];
inline int read(){
	int x=0;char ch=getchar();
	while (ch<'0'||ch>'9')ch=getchar();
	while (ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=getchar();
	return x;
}
int main(){
	int n=read(),a,sum=0;
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		sum+=(a=read());
		for(int j=0;j<MAXN;j++){
			dp[i&1][j]=0;
		}
		for(int j=0;j<MAXN;j++){
			dp[i&1][j]|=dp[!(i&1)][abs(j-a)];
			dp[i&1][abs(j-a)]|=dp[!(i&1)][j];
		}
	}
	for(int i=0;i<MAXN;i++)
		if(dp[n&1][i]){
			cout<<(sum-i>>1)<<' '<<(sum+i>>1);
			return 0;
		}
	return 0;
}