LQDDIV - Phân tập
Tác giả: hieult
Ngôn ngữ: C++
#include <cstdio>
//#include <conio.h>
typedef long long ll;
void Quicksort(ll A[],ll lower,ll upper)
{
ll x = A[(lower + upper) / 2];
ll i = lower;
ll j = upper;
do{
while(A[i] < x)
i ++;
while (A[j] > x)
j --;
if (i <= j)
{
ll tg=A[i];
A[i]=A[j];
A[j]=tg;
i ++;
j --;
}
}while(i <= j);
if (j > lower)
Quicksort(A, lower, j);
if (i < upper)
Quicksort(A, i, upper);
}
ll n,mu2[20],t,so,vitri;
ll a[35],b[100000],f[100000],d[100000],tong=0,tt,max,tim,tongtim,gan;
int main()
{
//freopen("LQDDIV1.in","r",stdin);
scanf("%lld",&n);
for(int i = 1;i<=n;i++) { scanf("%lld",&a[i]); tong+=a[i];}
ll m = n/2; ll k = n-m;
mu2[0] = 1; for(int i = 1;i<=20;i++) mu2[i] = mu2[i-1]<<1;
for(int i = 0;i<mu2[m];i++)
{
gan = i; tt = 0;
for(int j = 1;j<=m;j++){ if(gan%2==1) tt+= a[j]; gan/=2;}
b[i+1] = tt;
}
//printf("%lld\n",mu2[m]);
Quicksort(b,1,mu2[m]);
//for(int i = 1;i<=10;i++) printf("%lld ",b[i]);
t = 0;
for(int i = 1;i<=mu2[m];i++)
{
if(i==1)
{
f[++t] = b[i];
d[t] = 1;;
}
else
{
if(b[i]==b[i-1])
d[t]++;
else
{
f[++t] = b[i];
d[t] = 1;
}
}
}
//printf("%lld\n",tong);
max = 0;
for(int i = 0;i<mu2[k];i++)
{
gan = i; tt = 0;
for(int j = 1;j<=k;j++){ if(gan%2==1) tt+= a[j+m]; gan/=2;}
tim = tong/2 - tt;
//if(i<16000&& i>=15980) printf("%lld\n",tim);
//printf("%lld\n",tt);
if(tim<0) continue;
ll u = 1, v = t, r;
while(v-u>1)
{
r = (u+v)/2;
if(f[r]<=tim)
u = r;
else v = r;
//if(v!=0)
}
//ll p1 = 45000 ,p2 = 100000;
//if(tim == p1*p2 &&i<16000&& i>=15980) printf("%lld %lld\n",u,v);
if(f[v]<=tim)
{
tongtim = f[v]+tt;
vitri = v;
}
else
{
tongtim = f[u]+tt;
vitri = u;
}
//if(tim == p1*p2 &&i<16000&& i>=15980) printf("***%lld***\n",tongtim);
//if(tongtim%1000000000==0) printf("%lld %lld\n",u,v);
if(tongtim > max) {max = tongtim; so = d[vitri];}
else if(tongtim == max) {so+=d[vitri];}
}
//prllf("%d\n",tongtim);
if(max*2==tong) so/=2;
printf("%lld %lld",tong-2*max,so);
//getch();
}