LQDDIV - Phân tập

Tác giả: ll931110

Ngôn ngữ: C++

#include <iostream>
#include <cstdlib>
#define MAXV 65550
#define MAXN 33
using namespace std;

long long a[MAXV],b[MAXV],d[MAXV],kd[MAXV];
long long stmp,sum,u,delta;
int ta[MAXV],tb[MAXV],td[MAXV];
int na,nb,nd,n,tmpd,s[MAXN],k[MAXN],sup;

int compare_ints( const void* x, const void* y )
{  
     long long* arg1 = (long long*) x;
     long long* arg2 = (long long*) y;
     if( *arg1 < *arg2 ) return -1;
     else if( *arg1 == *arg2 ) return 0;
     else return 1;
}

void attempt(int i,int sup)
{
     for (int j = k[i - 1] + 1; j <= sup; j++)
     {
         k[i] = j;
         stmp += s[j];
         kd[++ nd] = stmp;
         
         if (j < sup) attempt(i + 1,sup);
         stmp -= s[j];
     }
}

void precalc()
{
     int i;
     
     nd = 0;
     stmp = 0;
     attempt(1,sup);
     
     qsort( kd, nd + 1, sizeof(long long), compare_ints);
     tmpd = 0;
     for (i = 0; i <= nd; i++) td[i] = 0;
     d[0] = 0;
     
     for (i = 0; i <= nd; i++)
       if (d[tmpd] == kd[i]) td[tmpd]++; 
       else
       {
           tmpd++;
           d[tmpd] = kd[i];
           td[tmpd] = 1;
       }
}


int main()
{
    int i,xa,xb;
    long long ncount;
    
    //freopen("lqddiv.inp","r",stdin);
    //freopen("lqddiv.out","w",stdout);
    
    scanf("%d", &n);
    sum = 0;
    for (i = 1; i <= n; i++) 
    {
        scanf("%d", &s[i]);
        sum += s[i];
    }
 
    sup = n/2;
    k[0] = 0;   
    precalc();
    na = tmpd;
    for (i = 0; i <= tmpd; i++) 
    {
        a[i] = d[i];
        ta[i] = td[i];
    }
    
    sup = n;
    k[0] = n/2;
    precalc();
    nb = tmpd;
    for (i = 0; i <= tmpd; i++) 
    {
        b[i] = d[i];
        tb[i] = td[i];
    }
    
    xa = 0;
    xb = nb;
    while (xb >= 0 && a[xa] + b[xb] > sum/2) xb--;      
    delta = a[xa] + b[xb];
    
    for (xa = 0; xa <= na; xa++)
    {
        while (xb >= 0 && a[xa] + b[xb] > sum/2) xb--;
        if (xb >= 0 && delta < a[xa] + b[xb]) delta = a[xa] + b[xb];
    }
    
    u = sum - 2 * delta;
    xa = 0;
    xb = nb;
    ncount = 0;
    
    while (xb >= 0 && a[xa] + b[xa] > delta) xb--;
    for (xa = 0; xa <= na; xa++)
    {
        while (xb >= 0 && a[xa] + b[xb] > delta) xb--;
        if (xb >= 0 && delta == a[xa] + b[xb]) ncount += ta[xa] * tb[xb];
    }
    
    if (u == 0) ncount = ncount/2;
    cout << u << " " << ncount;
}

Download