Решение задачи "Три части массива" с Codeforces

Без пояснения   Просмотров: 12

Задан массив 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 является максимально возможной.

Код 

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
	ll n,a[300000],ans=0,k=0;
	cin>>n;
	ll l=1,r=n,x=0;
	for(int i=1;i<=n;i++)cin>>a[i];
	while(r-l>=0){
		if(x>0)x-=a[r],k+=a[r],r--;
		else x+=a[l],l++;
		if(x==0)ans=max(ans,k);
	}
	if(x==0)ans=max(ans,k);
	cout<<ans;
}

         

Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться