首页 > 代码库 > Codeforces Round #266 (Div. 2) C. Number of Ways

Codeforces Round #266 (Div. 2) C. Number of Ways

2024-07-22 19:36:09   223人阅读

You‘ve got array a[1],?a[2],?...,?a[n], consisting ofn integers. Count the number of ways to split all the elements of the array into three contiguous parts so that the sum of elements in each part is the same.

More formally, you need to find the number of such pairs of indices i,?j (2?≤?i?≤?j?≤?n?-?1), that.

Input

The first line contains integer n (1?≤?n?≤?5·105), showing how many numbers are in the array. The second line containsn integers a[1],a[2], ..., a[n](|a[i]|?≤??109) — the elements of arraya.

Output

Print a single integer — the number of ways to split the array into three parts with the same sum.

Sample test(s)
Input
5
1 2 3 0 3
Output
2
Input
4
0 1 -1 0
Output
1
Input
2
4 1
Output
0题意：给你一个长为n的序列，让你分成三个子序列，使得三个子序列和相同，求方案数思路：首先要保证整个序列和是3的倍数，然后先从头找1/3的序列和的个数，然后再碰到2/3的序列和的话，就能确定它前面这个位置和1/3的位置可以再构成一个1/3，那么就能统计答案了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
using namespace std;
const int maxn = 500005;

ll sum[maxn];

int main() {
	int n;
	scanf("%d", &n);
	sum[0] = 0;
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		sum[i+1] = sum[i] + x;
	}

	ll ans = 0;
	if (sum[n] % 3 == 0) {
		ll one = sum[n] / 3, two = sum[n] / 3 * 2;
		ll cnt = 0;
		for (int i = 1; i < n; i++) {
			if (sum[i] == two)
				ans += cnt;
			if (sum[i] == one)
				cnt++;
		}
	}
	cout << ans << endl;
	return 0;
}


Codeforces Round #266 (Div. 2) C. Number of Ways


联系
我们