leafduo / vijos

solutions to vijos

This URL has Read+Write access

vijos / 1059 / 1059.cpp
100644 101 lines (84 sloc) 1.417 kb
raw blame history 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

//vijos 1059
 
//AC 向 vijos 抗议！
 
#define DEBUG
 
#include <iostream>
#include <bitset>
 
#ifdef DEBUG
#include <fstream>
#endif
 
using namespace std;
 
#ifdef DEBUG
ifstream fin("1059.in");
ofstream fout("1059.out");
#define cin fin
#define cout fout
#endif
 
const unsigned MAX=100;
 
 
int f[MAX+1][(MAX+1)*(MAX+1)];
int source[MAX+1][MAX];
int length[MAX+1];
unsigned N;
unsigned umax=MAX*MAX;
 
void input() {
	memset(f,0,sizeof(int)*(MAX+1)*(MAX+1));
	cin>>N;
	int i;
	int Max=0;
	for (int k=1;k<=N;k++) {
		for (i=0;;i++) {
			int temp;
			cin>>temp;
			if (temp!=-1) {
				Max+=temp;
				source[k][i]=temp;
			}
			else
				break;
		}
		if (Max<umax)
			umax=Max;
		length[k]=i;
	}
}
 
 
void DP() {
	for (int k=1;k<=N;k++) {
		f[k][0]=1;
		for (int j=0;j<length[k];j++)
			for (int i=umax;i>=0;i--) {
				if (i-source[k][j]>=0&&f[k][i-source[k][j]]) {
					f[k][i]=1;
					//break;
				}
			}
	}
}
 
inline bool isOK(unsigned n) {
	for (int i=1;i<=N;i++)
		if (!f[i][n])
            return false;
    return true;
}
 
unsigned status() {
    for (unsigned i=umax;i>=0;i--)
        if (isOK(i))
            return i;
    return 0;
}
 
#ifdef DEBUG
void print() {
    for (int i=1;i<=N;i++) {
        for (int j=0;j<=length[i];j++)
            cout<<source[i][j]<<" ";
        cout<<endl;
    }
}
#endif
 
int main() {
    input();
    DP();
    cout<<status()<<endl;
#ifdef DEBUG
    print();
#endif
    return 0;
}