Codeforces-466 C-Number of Ways-組合せ数学

https://codeforces.com/problemset/problem/466/C
データを均等な非空の3つのグループに分けるには,2番目の分割点を決定するたびに(それ以外の)1番目の分割点の数を加算すればよい.最後に3組目に少なくとも1つ残しておくのを覚えています.

#include
using namespace std;
#define ll long long

int n;
int a[500005];

int main(){
    scanf("%d",&n);
    for(int i=0;i)
        scanf("%d",&a[i]);

    ll sum=0;
    for(int i=0;i){
        sum+=a[i];
    }

    if(sum%3!=0){
        puts("0");
        return 0;
    }

    ll d=sum/3;
    int z1=0;

    ll cnt=0;

    ll cur=0;
    int inc=0;

    int i=0;
    while(i<n){
        cur+=a[i];
        if(cur==d){
            z1++;
            inc=1;
        }
        else{
            inc=0;
        }

        if(z1>=1){
            if(cur==2ll*d){
                if(i<=n-2){
                    //       n-1     
                    if(inc)
                        cnt+=z1-1;
                    else
                        cnt+=z1;
                    //printf("cnt=%lld i=%d
",cnt,i);
                }
            }
        }
        i++;
    }

    printf("%lld
",cnt);
}

 
転載先:https://www.cnblogs.com/Yinku/p/10397267.html