POJ2442 Sequence

n整数からなる集合がm個与えられて、おのおのから1個ずつ選んでその和をとった時にそれが小さい組み合わせから順にn個列挙せよという問題。

POJの鯖遅いしいくらなんでもO(mn^2log n)は通らないだろうなと思ってたら、怪しい二分探索のO(mnlog^2n)解を見つけたのでかく。AC。

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int map[100][2000];
int main()
{
	int data;
	scanf("%d",&data);
	for(int p=0;p<data;p++)
	{
		int mx,my;
		scanf("%d%d",&mx,&my);
		for(int i=0;i<mx;i++)
		{
			for(int j=0;j<my;j++)
			{
				scanf("%d",&map[i][j]);
			}
		}
		for(int i=0;i<mx;i++)
		{
			sort(map[i],map[i]+my);
		}
		int now[2000];
		for(int i=0;i<my;i++)
		{
			now[i]=map[0][i];
		}
		for(int i=1;i<mx;i++)
		{
			int beg=0,end=1000000;
			for(;;)
			{
				int med=(beg+end)/2;
				int ret=0;
				for(int j=0;j<my;j++)
				{
					int upp=upper_bound(map[i],map[i]+my,med-now[j])-map[i];
					ret+=upp;
				}
				//printf("%d %d %d %d\n",beg,end,med,ret);
				if(ret<my)
				{
					beg=med+1;
				}
				else
				{
					end=med;
				}
				if(beg==end)
				{
					break;
				}
			}
			int newnow[2000];
			int it=0;
			for(int j=0;j<my;j++)
			{
				for(int k=0;k<my;k++)
				{
					if(now[j]+map[i][k]>=beg)
					{
						break;
					}
					newnow[it]=now[j]+map[i][k];
					it++;
				}
			}
			for(;;)
			{
				if(it==my)
				{
					break;
				}
				newnow[it]=beg;
				it++;
			}
			sort(newnow,newnow+my);
			for(int j=0;j<my;j++)
			{
				now[j]=newnow[j];
			}
		}
		for(int i=0;i<my;i++)
		{
			if(i!=0)
			{
				printf(" ");
			}
			printf("%d",now[i]);
		}
		printf("\n");
	}
}