Slice and dice 2
Дан массив из n целых чисел. Требуется определить, удастся ли разделить этот массив на три непустые части таким образом, чтобы сумма каждой части была одинаковой.
Входные данные
Первая строка содержит целое число n — число элементов в массиве (1 ≤ n ≤ ).
Во второй строке расположены n целых чисел, разделённых пробелом, которые представляют элементы массива .
Выходные данные
Программа должна вывести Yes, если есть способ разбить массив в двух местах на три непустые части с одинаковыми суммами, и No — в противном случае.
Примеры
Входные данные | Выходные данные |
|---|---|
5 3 2 1 3 0 | Yes |
4 5 -1 0 6 | No |
Пояснение
[3] [2, 1] [3, 0] ⇒ каждая часть имеет сумму 3
Нельзя найти разбиение на три части с одинаковой суммой
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB