백준 19942번 - 다이어트

www.acmicpc.net/problem/19942

19942번: 다이어트

[ 2020년도 한국정보올림피아드 1차대회 중등부 2번 다이어트 소스 코드 ]

#include <stdio.h>

int A[20],B[20],C[20],D[20],E[20];
int n,a,b,c,d,e=11111111;
int x[20],z,f[20];
bool check[20];

void go(int a1,int b1,int c1,int d1,int e1,int y,int k)
{
	if(e1>e)
		return;
	if(a1>=a && b1>=b && c1>=c && d1>=d && e1<e)
	{
		z=y;
		e=e1;
		for(int j=0;j<y;j++)
		{
			f[j]=x[j];
		}
		return;
	}
	for(int i=k;i<n;i++)
	{
		if(check[i]==false)
		{
			check[i]=true;
			a1=a1+A[i];
			b1=b1+B[i];
			c1=c1+C[i];
			d1=d1+D[i];
			e1=e1+E[i];
			x[y]=i+1;
			go(a1,b1,c1,d1,e1,y+1,i);
			a1=a1-A[i];
			b1=b1-B[i];
			c1=c1-C[i];
			d1=d1-D[i];
			e1=e1-E[i];
			check[i]=false;
		}
	}
}
int main()
{
	int i,X=0,Y=0,Z=0,O=0;
	scanf("%d",&n);
	scanf("%d %d %d %d",&a,&b,&c,&d);
	
	for(i=0;i<n;i++)
	{
		scanf("%d %d %d %d %d",&A[i],&B[i],&C[i],&D[i],&E[i]);
		X=X+A[i];
		Y=Y+B[i];
		Z=Z+C[i];
		O=O+D[i];
	}
	
	if(X<a || Y<b || Z<c || O<d)
	{
		printf("-1");
		return 0;
	}
	
	go(0,0,0,0,0,0,0);
	
	printf("%d\n",e);
	for(i=0;i<z;i++)
	{
		printf("%d ",f[i]);
	}
}