Submission #2429089

---

Source Code Expand

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <numeric>
#include <queue>
#include <map> 
#include <set>
#include <string>
#include <functional>
#include <list>
#define ll long long
#define oku7 1000000007
#define MAXN (int)1e+5 * 2+1
using namespace std;

char mapData[100][100];
int costData[100][100];
ll imos[MAXN];
ll input[MAXN];
int dx[4] = { 0, 1, 0,-1 }; // x軸方向への変位
int dy[4] = { 1, 0,-1, 0 }; // y軸方向への変位

ll nC2(ll n) {
	if (n <= 1) return 0;
	return n * (n - 1) / 2;
}

int main() {
	ll N;
	cin >> N;
	for (ll i = 0; i < N; i++) {
		ll a;
		cin >> a;
		input[i] = a;
	}

	//累積和をとる
	imos[0] = input[0];
	for (ll i = 1; i < N; i++) {
		imos[i] = input[i] + imos[i - 1];
	}
	//同じものの個数を数える
	map<ll, ll> m;
	set<ll> s;
	for (ll i = 0; i < N; i++) {
		s.insert(imos[i]);
		if (m[imos[i]] == 0) m[imos[i]] = 1;
		else m[imos[i]]++;
	}

	ll ans = m[0];
	for (ll l : s) {
		ans+= nC2(m[l]);
	}

	cout << ans << "\n";
	return 0;
}

Submission Info

Judge Result