Tuenti Contest 5 (Pablo Moreno)

/*
    Author: Pablo Moreno Olalla
    Email address: darthbrevu@yahoo.es
*/
#include <set>
#include <deque>
#include <cstdio>
#include <string>
#include <vector>
#include <fstream>
#include <sstream>
#include <iostream>
#include <algorithm>

using namespace std;

//This is actually a VERY common problem in computer science academia, slightly reformuled.
//Its typical solution always yields the optimal result; however, it can be very costly in space and time.
//With the intelligent use of deques we can greatly reduce the amount of memory usage.

struct Cow  {
public:
    unsigned int weight;
    unsigned int milk;
};

class DequeMatrix   {
private:
    class DequeElement  {
    public:
        unsigned int usedWeight;
        unsigned int milk;
        bool thisUsed;
    };
    vector<deque<DequeElement> > data;
    unsigned int maxToStore;
    unsigned int firstIndex;
    const vector<Cow> &cows;
public:
    inline DequeMatrix(const vector<Cow> &c):data(vector<deque<DequeElement> >(c.size(),deque<DequeElement>(0))),maxToStore(0),firstIndex(0),cows(c)    {
        for (size_t i=0;i<cows.size();++i) maxToStore=max(maxToStore,cows[i].weight);
        maxToStore++;
        //An even more efficient method would have been creating circular vectors of 2*maxToStore size and
        //move through them using pointers or accessors. However, I felt it was a little too much.
        //Actually, I think deque does that internally.
    }
    inline void start() {
        for (size_t i=0;i<cows.size();++i) data[i].resize(1);
        if (cows[0].weight<=1)  {
            data[0][0].usedWeight=cows[0].weight;
            data[0][0].milk=cows[0].milk;
            data[0][0].thisUsed=true;
        }   else    {
            data[0][0].usedWeight=0;
            data[0][0].milk=0;
            data[0][0].thisUsed=false;
        }
        for (size_t i=1;i<cows.size();++i) if (cows[0].weight<=1&&cows[0].milk>data[i-1][0].milk)   {
            data[i][0].usedWeight=cows[i].weight;
            data[i][0].milk=cows[i].milk;
            data[i][0].thisUsed=true;
        }   else    {
            data[i][0].usedWeight=data[i-1][0].usedWeight;
            data[i][0].milk=data[i-1][0].milk;
            data[i][0].thisUsed=false;
        }
        firstIndex=1;
    }
    void advanceColumn()    {
        size_t N=data[0].size();
        data[0].resize(N+1);
        if (!data[0][N-1].thisUsed&&(N+firstIndex==cows[0].weight)) {
            data[0][N].usedWeight=cows[0].weight;
            data[0][N].milk=cows[0].milk;
            data[0][N].thisUsed=true;
        }   else data[0][N]=data[0][N-1];
        unsigned int mmU,mmL;
        bool canAddU,canAddL;
        for (size_t i=1;i<cows.size();++i)  {
            data[i].resize(N+1);
            canAddU=data[i-1][N].usedWeight+cows[i].weight<=N+firstIndex;
            canAddL=(!data[i][N-1].thisUsed)&&(data[i][N-1].usedWeight+cows[i].weight<=N+firstIndex);
            mmU=data[i-1][N].milk+(canAddU?cows[i].milk:0);
            mmL=data[i][N-1].milk+(canAddL?cows[i].milk:0);
            if (mmL>=mmU)   {
                data[i][N]=data[i][N-1];
                if (canAddL)    {
                    data[i][N].usedWeight+=cows[i].weight;
                    data[i][N].milk+=cows[i].milk;
                    data[i][N].thisUsed=true;
                }
            }   else    {
                data[i][N]=data[i-1][N];
                if (canAddU)    {
                    data[i][N].usedWeight+=cows[i].weight;
                    data[i][N].milk+=cows[i].milk;
                    data[i][N].thisUsed=true;
                }
            }
        }
        if (N>=maxToStore)  {
            for (size_t i=0;i<cows.size();++i) data[i].pop_front();
            firstIndex++;
        }
    }
    inline unsigned int getResult() const   {
        return data.back().back().milk;
    }
};

unsigned int dynaProg(unsigned int maxW,const vector<Cow> &data)    {
    DequeMatrix dm(data);
    dm.start();
    for (int i=1;i<maxW;++i) dm.advanceColumn();
    return dm.getResult();
}

bool funString(const string &in,unsigned int &res)  {
    unsigned int N;
    unsigned int maxW;
    static vector<Cow> data(0);
    istringstream iss(in);
    iss>>N>>maxW;
    if (iss.fail()) return false;
    data.resize(N);
    for (size_t i=0;i<N;++i)    {
        iss.ignore(1);
        iss>>data[i].weight;
    }
    vector<size_t> rem(0);
    rem.reserve(N);
    for (size_t i=0;i<N;++i)    {
        iss.ignore(1);
        iss>>data[i].milk;
        if (data[i].milk==0) rem.push_back(i);
    }
    if (iss.fail()) return false;
    //Now, let's remove cows with zero milk. They're useless!
    for (vector<size_t>::const_reverse_iterator rit=rem.rbegin();rit!=rem.rend();++rit) data.erase(data.begin()+(*rit));
    N-=rem.size();
    rem.clear();
    if (data.size()==0) {
        res=0;
        return true;
    }
    //This is a shortcut! Who knows, maybe the problem is trivial.
    unsigned int totalW=0;
    for (size_t i=0;i<N;++i) totalW+=data[i].weight;
    if (totalW<=maxW)   {
        res=0;
        for (size_t i=0;i<N;++i) res+=data[i].milk;
        return true;
    }
    //The shortcut didn't work. Time to do the dirty work by hand.
    res=dynaProg(maxW,data);
    return true;
}

int main(int argc,char **argv)  {
    //The first two lines are not strictly necessary, but make the code a little more handy.
    if (argc>=2) freopen(argv[1],"r",stdin);
    if (argc>=3) freopen(argv[2],"w",stdout);
    string tmp;
    unsigned int res;
    do  {
        getline(cin,tmp);
        if (funString(tmp,res)) cout<<res<<endl;
    }   while (!cin.eof()&&!cin.fail());
    return 0;
}