Vijos 1059 (C)

p1059.vijos.c

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define maxn 110
#define sqrmaxn 12100

int n;
bool f[maxn][sqrmaxn];

int max(int p, int q) {
	return p>q?p:q;
}

bool check(int p) {
	int i;
	for (i=1; i<=n; i++) 
		if (!f[i][p]) return false;
	return true;
}

int main() {
	int a[maxn];
	int i,maxsum=0;
    	scanf("%d",&n);
	for (i=1; i<=n; i++) {
		int m=1,j,k,sum;
		memset(a,0,sizeof(a));
		scanf("%d",&(a[m]));
		while (a[m]!=-1) scanf("%d",&(a[++m]));
		for (m--,j=1,sum=0; j<=m; sum+=a[j++]);
		f[i][0]=true;
		for (j=1; j<=m; j++)
			for (k=sum; k>=a[j]; k--)
				f[i][k]|=f[i][k-a[j]];
		maxsum=max(sum,maxsum);
	}
	int ans=maxsum;
	while (!check(ans) && ans>0) ans--;
	printf("%d\n",ans);
	return 0;
}