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;
}