Решение задачи Три части массива с Codeforces
Без пояснения   Просмотров: 123
Задан массив d1,d2,…,dn, состоящий из n целых чисел.
Ваша задача — разделить этот массив на три части (некоторые из которых могут быть пустыми) таким образом, что каждый элемент массива принадлежит ровно одной из частей, и каждая часть образует последовательный непрерывный подотрезок (возможно, пустой) изначального массива.
Пусть сумма элементов первой части равна sum1, сумма элементов второй части равна sum2 и сумма элементов третьей части равна sum3. Среди всех возможных разбиений массива вам нужно выбрать такое, что sum1=sum3 и sum1 является максимально возможной.
Более формально, если первая часть массива содержит a элементов, вторая часть массива содержит b элементов и третья часть массива содержит c элементов, тогда:
sum1=∑1≤i≤adi,
sum2=∑a+1≤i≤a+bdi,
sum3=∑a+b+1≤i≤a+b+cdi.
Сумма пустого массива равна 0.
Ваша задача найти такое разбиение массива, что sum1=sum3 и sum1 является максимально возможной.
Ваша задача — разделить этот массив на три части (некоторые из которых могут быть пустыми) таким образом, что каждый элемент массива принадлежит ровно одной из частей, и каждая часть образует последовательный непрерывный подотрезок (возможно, пустой) изначального массива.
Пусть сумма элементов первой части равна sum1, сумма элементов второй части равна sum2 и сумма элементов третьей части равна sum3. Среди всех возможных разбиений массива вам нужно выбрать такое, что sum1=sum3 и sum1 является максимально возможной.
Более формально, если первая часть массива содержит a элементов, вторая часть массива содержит b элементов и третья часть массива содержит c элементов, тогда:
sum1=∑1≤i≤adi,
sum2=∑a+1≤i≤a+bdi,
sum3=∑a+b+1≤i≤a+b+cdi.
Сумма пустого массива равна 0.
Ваша задача найти такое разбиение массива, что sum1=sum3 и sum1 является максимально возможной.