记录编号	618781	评测结果	AAAAAAAAAA
题目名称	4480.分饼干	最终得分	100
用户昵称	xuyuqing	是否通过	通过
代码语言	C++	运行时间	2.829 s
提交时间	2026-09-12 14:39:59	内存使用	20.54 MiB

 
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
 
using namespace std;
 
const int N = 55;
const int Maxn = 500010;
 
int n;
int nums[N];
int sum;
int dp[2][3][(Maxn << 1) + 10]; // 0: Francin 1: Nilly 2: Mom
 
int main () {
	
	freopen ("cookie.in", "r", stdin);
	freopen ("cookie.out", "w", stdout);
	
	scanf ("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf ("%d", &(nums[i]));
		sum += nums[i];
	}
	
	for (int i = 0; i <= 1; i++) {
		for (int opt = 0; opt < 3; opt++) {
			for (int bigger = -sum; bigger <= sum; bigger++) {
				dp[i][opt][bigger + Maxn] = -1e9;
			}
		}	
	}
	dp[0][0][Maxn] = dp[0][1][Maxn] = dp[0][2][Maxn] = 0;
	for (int i = 1; i <= n; i++) {
		for (int opt = 0; opt < 3; opt++) {
			for (int bigger = -sum; bigger <= sum; bigger++) {
				// Francine:
				if (bigger + nums[i] <= sum) {
					dp[i & 1][0][bigger + nums[i] + Maxn] = 
					max (dp[i & 1][0][bigger + nums[i] + Maxn], dp[(i - 1) & 1][opt][bigger + Maxn] + nums[i]);
				}
				
				// Nilly:
				if (bigger - nums[i] >= -sum) {
					dp[i & 1][1][bigger - nums[i] + Maxn] =
					max (dp[i & 1][1][bigger - nums[i] + Maxn], dp[(i - 1) & 1][opt][bigger + Maxn]);
				}
				
				// Mom:
				dp[i & 1][2][bigger + Maxn] = max (dp[i & 1][2][bigger + Maxn], dp[(i - 1) & 1][opt][bigger + Maxn]);
			}
		}
	}
	
//	for (int i = 1; i <= n; i++) {
//		cout << i << " id" << endl;
//		for (int opt = 0; opt < 3; opt++) {
//			cout << opt << " opt" << endl;
//			for (int bigger = -sum; bigger <= sum; bigger++) {
//				cout << bigger << " : " << dp[i][opt][bigger + Maxn] << endl;
//			}
//		}
//	}
	
	cout << max ({dp[n & 1][0][Maxn], dp[n & 1][1][Maxn], dp[n & 1][2][Maxn]}) << endl;
	
	return 0;
}