Zero Array---思维题

链接 submit

B. Zero Array

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array a1,a2,…,ana1,a2,…,an.

In one operation you can choose two elements aiai and ajaj (i≠ji≠j) and decrease each of them by one.

You need to check whether it is possible to make all the elements equal to zero or not.

Input

The first line contains a single integer nn (2≤n≤1052≤n≤105) — the size of the array.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109) — the elements of the array.

Output

Print "YES" if it is possible to make all elements zero, otherwise print "NO".

Examples

input

Copy

4

1 1 2 2

output

Copy

YES

input

Copy

6

1 2 3 4 5 6

output

Copy

NO

Note

In the first example, you can make all elements equal to zero in 33 operations:

Decrease a1a1 and a2a2,
Decrease a3a3 and a4a4,
Decrease a3a3 and a4a4

In the second example, one can show that it is impossible to make all elements equal to zero.

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string.h>

#include<vector>

#include<cmath>

#include<string>

#include<map>

#include<queue>

using namespace std;

typedef long long ll;

ll num[100001],n;

//priority_queue<ll,vector<ll>,less<ll> > p;

int main(){

	while(~scanf("%lld",&n)){

		ll sum=0,max_k=-1;

	for(ll i=1;i<=n;i++){

		scanf("%lld",&num[i]);

		sum+=num[i];

		max_k=max(max_k,num[i]);

	}

	//如果总和不是偶数，或者最大值比总和的一半大，不能实现

	if(sum%2==1||max_k>sum/2){

		printf("NO\n");

		continue;

	}

	else {

		printf("YES\n");

		continue;

	}

}

	return 0;

}

//            /\       |  /  |**、

//			 /  \      | /   |   \

//			/    \     |/    |   /  _____                      ____   |  /

//		   /------\    |\    |__/  /     \  \      /\      /  /    \  | /

//		  /        \   | \   |    /       \  \    /  \    /  /______\ |/

//		 /          \  |  \  |    \       /   \  /    \  /   \        |

//      /            \ |   \ |     \_____/     \/      \/     \_____  |

/**

 *　　　　　　　　┏┓　　 　┏┓

 * 　　　　　　　┏┛┗━━━━━━━┛┗━━━┓

 * 　　　　　　　┃　　　　　　　┃ 　

 * 　　　　　　　┃　　　━　　 　┃

 * 　　　　　　　┃　＞　　　＜　┃

 * 　　　　　　　┃　　　　　　　┃

 * 　　　　　　　┃...　⌒　... 　┃

 * 　　　　　　　┃　　　　　　　┃

 * 　　　　　　　┗━┓　　　┏━┛

 * 　　　　　　　　　┃　　　┃　Code is far away from bug with the animal protecting　　　　　　　　　　

 * 　　　　　　　　　┃　　　┃   神兽保佑,代码无bug

 * 　　　　　　　　　┃　　　┃　　　　　　　　　　　

 * 　　　　　　　　　┃　　　┃  　　　　　　

 * 　　　　　　　　　┃　　　┃

 * 　　　　　　　　　┃　　　┃　　　　　　　　　　　

 * 　　　　　　　　　┃　　　┗━━━┓

 * 　　　　　　　　　┃　　　　　　　┣┓

 * 　　　　　　　　　┃　　　　　　　┏┛

 * 　　　　　　　　　┗┓┓┏━┳┓┏┛

 * 　　　　　　　　　　┃┫┫　┃┫┫

 * 　　　　　　　　　　┗┻┛　┗┻┛

 */

// warm heart, wagging tail,and a smile just for you!

//

//                            _ooOoo_

//                           o8888888o

//                           88" . "88

//                           (| -_- |)

//                           O\  =  /O

//                        ____/`---'\____

//                      .'  \|     |//  `.

//                     /  \|||  :  |||//  \

//                    /  _||||| -:- |||||-  \

//                    |   | \\  -  /// |   |

//                    | \_|  ''\---/''  |   |

//                    \  .-\__  `-`  ___/-. /

//                  ___`. .'  /--.--\  `. . __

//               ."" '<  `.___\_<|>_/___.'  >'"".

//              | | :  `- \`.;`\ _ /`;.`/ - ` : | |

//              \  \ `-.   \_ __\ /__ _/   .-` /  /

//         ======`-.____`-.___\_____/___.-`____.-'======

//                            `=---='

//        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

//

巴特西

Zero Array---思维题

最新文章

热门文章