castle.cpp

#include <cstdlib>
#include <cstring>
#include <cstdio>
#define MAX_CASTLE 102
#define MAX_HEIGHT 10002
#define fin stdin
#define fout stdout

int n; 
int min_height = 0x7FFFFFFF; 
int castle[MAX_CASTLE][MAX_CASTLE]; 
bool f[MAX_CASTLE][MAX_HEIGHT]; 
int prev[MAX_CASTLE][MAX_HEIGHT]; 

inline int fmin(int a, int b) {
    return a < b ? a : b; 
}

void dp(int no) {
    int max_puzzle = 0; 
    int max_height = 0; 
    for(int i = 0; true; i++) {
        if(!castle[no][i]) {
            break; 
        }
        max_height = max_height + castle[no][i]; 
        max_puzzle = max_puzzle + 1; 
    }
    for(int i = 0; i < max_puzzle; i++) {
        for(int j = max_height; j >= castle[no][i]; j--) {
            if(f[no][j - castle[no][i]]) {
                f[no][j] = true; 
                prev[no][j] = i; 
            }
        }
        f[no][castle[no][i]] = true; 
    }
    min_height = fmin(max_height, min_height); 
}

int main() {
//    FILE *fin = fopen("castle.in", "r"); 
//    FILE *fout = fopen("castle.out", "w"); 
    int a, b; 
    bool flag; 
    fscanf(fin, "%d", &n); 
    for(int i = 0; i < n; i++) {
        memset(castle[i], 0, sizeof(castle[i])); 
        memset(f[i], 0, sizeof(f[i])); 
        b = 0; 
        while(true) {
            fscanf(fin, "%d", &a); 
            if(a == -1) {
                break; 
            }
            castle[i][b++] = a; 
        }
    }
    for(int i = 0; i < n; i++) {
        dp(i); 
    }
    for(int i = min_height; i >= 0; i--) {
        flag = true; 
        for(int j = 0; j < n; j++) {
            if(!f[j][i]) {
                flag = false; 
                break; 
            }
        }
        if(flag) {
            fprintf(fout, "%d\n", i); 
            return 0; 
        }
    }
    fprintf(fout, "0\n"); 
    return 0; 
}