zoj 1794 Merging Sequences Pr...

zoj 1794 Merging Sequences Pr...

#include<iostream>#include<string>#include<set>#include<cstdio>#include<cstring>using namespace std;enum {    SIZ = 104,    LIM = 999999999,};int dat[SIZ];struct Node;struct Object {    int hs, sum;    int no;    Node *ptr;    bool operator < (const Object &o) const {        return max(hs, sum + o.hs) < max(o.hs, o.sum + hs);    }};Object sys;struct Node {    int num;    Object obj[SIZ];    void gen(){        int pos = 0, i=0;        memset(obj, 0, sizeof(obj));        while(i < num && dat[i] <= 0){ sys.sum += dat[i]; ++i;        }        while(i < num){ while(i<num&&dat[i]>=0){     obj[pos].hs += dat[i];     obj[pos].sum += dat[i];     ++i; } while(i<num&&dat[i]<=0){     obj[pos].sum += dat[i];     ++i; } obj[pos].ptr = this; obj[pos].no = pos; ++pos;        }        num = pos;    }    int readIn() {        num = 0;        scanf("%d", &dat[num]);        while(dat[num]!=9999 && dat[num]!=-9999){ ++num; scanf("%d", &dat[num]);        }        return dat[num] == 9999;    }};int sn;Node tree[6];void fun(){    set<Object> os;    for (int i=0; i<sn; ++i){        if (tree[i].num){ os.insert(tree[i].obj[0]);        }    }    while(!os.empty()){        Object cur = *os.begin();        os.erase(os.begin());        int hs = sys.sum + cur.hs;        if (hs > sys.hs){ sys.hs = hs;        }        sys.sum += cur.sum;        int no = cur.no + 1;        if (no < cur.ptr->num){ os.insert(cur.ptr->obj[no]);        }    }    printf("%dn", sys.hs);}void readIn(){    memset(&sys, 0, sizeof(sys));    sn = 0;    while(tree[sn].readIn()){        tree[sn].gen();        ++sn;    }    tree[sn].gen();    ++sn;}int main(){    int tn;    scanf("%d", &tn);    while(tn-- > 0){        readIn();        fun();    }    return 0;}