Nbrevu

Tuenti Contest 5 (Pablo Moreno)

Jun 20th, 2011
1,118
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.     Author: Pablo Moreno Olalla
  3.     Email address: darthbrevu@yahoo.es
  4. */
  5. #include <set>
  6. #include <deque>
  7. #include <cstdio>
  8. #include <string>
  9. #include <vector>
  10. #include <fstream>
  11. #include <sstream>
  12. #include <iostream>
  13. #include <algorithm>
  14.  
  15. using namespace std;
  16.  
  17. //This is actually a VERY common problem in computer science academia, slightly reformuled.
  18. //Its typical solution always yields the optimal result; however, it can be very costly in space and time.
  19. //With the intelligent use of deques we can greatly reduce the amount of memory usage.
  20.  
  21. struct Cow  {
  22. public:
  23.     unsigned int weight;
  24.     unsigned int milk;
  25. };
  26.  
  27. class DequeMatrix   {
  28. private:
  29.     class DequeElement  {
  30.     public:
  31.         unsigned int usedWeight;
  32.         unsigned int milk;
  33.         bool thisUsed;
  34.     };
  35.     vector<deque<DequeElement> > data;
  36.     unsigned int maxToStore;
  37.     unsigned int firstIndex;
  38.     const vector<Cow> &cows;
  39. public:
  40.     inline DequeMatrix(const vector<Cow> &c):data(vector<deque<DequeElement> >(c.size(),deque<DequeElement>(0))),maxToStore(0),firstIndex(0),cows(c)    {
  41.         for (size_t i=0;i<cows.size();++i) maxToStore=max(maxToStore,cows[i].weight);
  42.         maxToStore++;
  43.         //An even more efficient method would have been creating circular vectors of 2*maxToStore size and
  44.         //move through them using pointers or accessors. However, I felt it was a little too much.
  45.         //Actually, I think deque does that internally.
  46.     }
  47.     inline void start() {
  48.         for (size_t i=0;i<cows.size();++i) data[i].resize(1);
  49.         if (cows[0].weight<=1)  {
  50.             data[0][0].usedWeight=cows[0].weight;
  51.             data[0][0].milk=cows[0].milk;
  52.             data[0][0].thisUsed=true;
  53.         }   else    {
  54.             data[0][0].usedWeight=0;
  55.             data[0][0].milk=0;
  56.             data[0][0].thisUsed=false;
  57.         }
  58.         for (size_t i=1;i<cows.size();++i) if (cows[0].weight<=1&&cows[0].milk>data[i-1][0].milk)   {
  59.             data[i][0].usedWeight=cows[i].weight;
  60.             data[i][0].milk=cows[i].milk;
  61.             data[i][0].thisUsed=true;
  62.         }   else    {
  63.             data[i][0].usedWeight=data[i-1][0].usedWeight;
  64.             data[i][0].milk=data[i-1][0].milk;
  65.             data[i][0].thisUsed=false;
  66.         }
  67.         firstIndex=1;
  68.     }
  69.     void advanceColumn()    {
  70.         size_t N=data[0].size();
  71.         data[0].resize(N+1);
  72.         if (!data[0][N-1].thisUsed&&(N+firstIndex==cows[0].weight)) {
  73.             data[0][N].usedWeight=cows[0].weight;
  74.             data[0][N].milk=cows[0].milk;
  75.             data[0][N].thisUsed=true;
  76.         }   else data[0][N]=data[0][N-1];
  77.         unsigned int mmU,mmL;
  78.         bool canAddU,canAddL;
  79.         for (size_t i=1;i<cows.size();++i)  {
  80.             data[i].resize(N+1);
  81.             canAddU=data[i-1][N].usedWeight+cows[i].weight<=N+firstIndex;
  82.             canAddL=(!data[i][N-1].thisUsed)&&(data[i][N-1].usedWeight+cows[i].weight<=N+firstIndex);
  83.             mmU=data[i-1][N].milk+(canAddU?cows[i].milk:0);
  84.             mmL=data[i][N-1].milk+(canAddL?cows[i].milk:0);
  85.             if (mmL>=mmU)   {
  86.                 data[i][N]=data[i][N-1];
  87.                 if (canAddL)    {
  88.                     data[i][N].usedWeight+=cows[i].weight;
  89.                     data[i][N].milk+=cows[i].milk;
  90.                     data[i][N].thisUsed=true;
  91.                 }
  92.             }   else    {
  93.                 data[i][N]=data[i-1][N];
  94.                 if (canAddU)    {
  95.                     data[i][N].usedWeight+=cows[i].weight;
  96.                     data[i][N].milk+=cows[i].milk;
  97.                     data[i][N].thisUsed=true;
  98.                 }
  99.             }
  100.         }
  101.         if (N>=maxToStore)  {
  102.             for (size_t i=0;i<cows.size();++i) data[i].pop_front();
  103.             firstIndex++;
  104.         }
  105.     }
  106.     inline unsigned int getResult() const   {
  107.         return data.back().back().milk;
  108.     }
  109. };
  110.  
  111. unsigned int dynaProg(unsigned int maxW,const vector<Cow> &data)    {
  112.     DequeMatrix dm(data);
  113.     dm.start();
  114.     for (int i=1;i<maxW;++i) dm.advanceColumn();
  115.     return dm.getResult();
  116. }
  117.  
  118. bool funString(const string &in,unsigned int &res)  {
  119.     unsigned int N;
  120.     unsigned int maxW;
  121.     static vector<Cow> data(0);
  122.     istringstream iss(in);
  123.     iss>>N>>maxW;
  124.     if (iss.fail()) return false;
  125.     data.resize(N);
  126.     for (size_t i=0;i<N;++i)    {
  127.         iss.ignore(1);
  128.         iss>>data[i].weight;
  129.     }
  130.     vector<size_t> rem(0);
  131.     rem.reserve(N);
  132.     for (size_t i=0;i<N;++i)    {
  133.         iss.ignore(1);
  134.         iss>>data[i].milk;
  135.         if (data[i].milk==0) rem.push_back(i);
  136.     }
  137.     if (iss.fail()) return false;
  138.     //Now, let's remove cows with zero milk. They're useless!
  139.     for (vector<size_t>::const_reverse_iterator rit=rem.rbegin();rit!=rem.rend();++rit) data.erase(data.begin()+(*rit));
  140.     N-=rem.size();
  141.     rem.clear();
  142.     if (data.size()==0) {
  143.         res=0;
  144.         return true;
  145.     }
  146.     //This is a shortcut! Who knows, maybe the problem is trivial.
  147.     unsigned int totalW=0;
  148.     for (size_t i=0;i<N;++i) totalW+=data[i].weight;
  149.     if (totalW<=maxW)   {
  150.         res=0;
  151.         for (size_t i=0;i<N;++i) res+=data[i].milk;
  152.         return true;
  153.     }
  154.     //The shortcut didn't work. Time to do the dirty work by hand.
  155.     res=dynaProg(maxW,data);
  156.     return true;
  157. }
  158.  
  159. int main(int argc,char **argv)  {
  160.     //The first two lines are not strictly necessary, but make the code a little more handy.
  161.     if (argc>=2) freopen(argv[1],"r",stdin);
  162.     if (argc>=3) freopen(argv[2],"w",stdout);
  163.     string tmp;
  164.     unsigned int res;
  165.     do  {
  166.         getline(cin,tmp);
  167.         if (funString(tmp,res)) cout<<res<<endl;
  168.     }   while (!cin.eof()&&!cin.fail());
  169.     return 0;
  170. }
RAW Paste Data