Решение задачи "Евгений и массив" с Codeforces

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


Евгений любит работать с массивами. Сегодня ему нужна ваша помощь, чтобы решить одну сложную задачку.

Массив c является подмассивом b, если c может быть получен из b удалением нескольких (возможно, ни одного или всех) элементов из начала и нескольких (возможно, ни одного или всех) элементов из конца.

Назовем непустой массив хорошим, если для любого непустого подмассива этого массива, сумма его элементов не равна нулю. К примеру, массив [−1,2,−3] является хорошим, так как все массивы [−1], [−1,2], [−1,2,−3], [2], [2,−3], [−3] имеют ненулевую сумму элементов. В то же время, массив [−1,2,−1,−3] не является хорошим, так как его подмассив [−1,2,−1] имеет сумму элементов равную 0.

Помогите Евгению посчитать количество непустых хороших подмассивов данного массива a.

Код

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

#define ll long long

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	ll n, i=0, x, ans=0, sum=0, res=0;
	cin >> n;
	map<ll,ll>mp;
	mp[0] = 1;

	while(n--) {
		i++;
		cin >> x;
		sum += x;
		res = max(res, mp[sum]);
		ans += i - res;
		mp[sum] = i+1;
	}
	cout << ans;
}

         

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


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

Комментарии

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