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

You've got array a[1], a[2], ..., a[n], consisting of n 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 contains n integers a[1], a[2], ..., a[n] (|a[i]| ≤ 109) — the elements of array a.
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

Input

4
0 1 -1 0

Output

Input

2
4 1

Output

사고방식: 만약에 여러 가지 상황으로 나뉘면 전체(SUM)를 고려하여 SUM/3을 분석해야 한다.그것은 3단을 구분하는 표준이다.그래서 부분과 tmp==SUM/3을 합치면 부분 통계는 1을 더한다.
tmp=sUM*2/3이면 모두ans+=부분통계(s)를 통계한다.

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<algorithm>
#define LL  __int64
#define inf 0x3f3f3f3f
using namespace std;
LL a[1000000];
int main()
{
    LL n,m,i,j,k;
    LL b,t;
    while(~scanf("%I64d",&n))
    {
        LL z=0;
        for(i=0;i<n;i++)
        {
            scanf("%I64d",&a[i]);
            z+=a[i];
        }
        if(z%3)
        {
            printf("0
");
            continue;
        }
        z/=3;
        LL ans=0;LL s=0;LL tmp=0;
        for(i=0;i<n-1;i++)//         <span id="transmark"></span>
        {
            tmp+=a[i];
            if(z*2==tmp)
            {
                ans+=s;
            }
            if(z==tmp)
            {
                s++;
            }
        }
        printf("%I64d
",ans);
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[HDU 5608] function

Problem Description There is a function f(x),which is defined on the natural numbers set N,satisfies the following eqaut...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

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

좋은 웹페이지 즐겨찾기