• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added SRM/528/1A.cpp version [1f7e5221dd3ee508]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <cstring>
           18  +#ifdef __GNUC__
           19  +#include <ext/hash_map>
           20  +#define unordered_map __gnu_cxx::hash_map
           21  +#else
           22  +#include <unordered_map>
           23  +#endif
           24  +using namespace std;
           25  +typedef long long LL;
           26  +typedef complex<double> CMP;
           27  +
           28  +class Cut { public:
           29  + static bool TensFirst(int a, int b)
           30  + {
           31  +  if(a%10 != b%10)
           32  +   return a%10 < b%10;
           33  +  return a < b;
           34  + }
           35  +
           36  + int getMaximum(vector <int> eelLengths, int maxCuts)
           37  + {
           38  +  sort(eelLengths.begin(), eelLengths.end(), &TensFirst);
           39  +
           40  +  int una = 0;
           41  +  for(int i=0; i<eelLengths.size(); ++i) {
           42  +   int e = eelLengths[i];
           43  +   while( maxCuts && e>10 )
           44  +    una++, maxCuts--, e-=10;
           45  +   if( e == 10 )
           46  +    una++;
           47  +  }
           48  +  return una;
           49  + }
           50  +};
           51  +
           52  +// BEGIN CUT HERE
           53  +#include <ctime>
           54  +double start_time; string timer()
           55  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           56  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           57  + { os << "{ ";
           58  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           59  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           60  +void verify_case(const int& Expected, const int& Received) {
           61  + bool ok = (Expected == Received);
           62  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           63  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           64  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           65  +#define END  verify_case(_, Cut().getMaximum(eelLengths, maxCuts));}
           66  +int main(){
           67  +
           68  +CASE(0)
           69  + int eelLengths_[] = {13, 20, 13};
           70  +   vector <int> eelLengths(eelLengths_, eelLengths_+sizeof(eelLengths_)/sizeof(*eelLengths_));
           71  + int maxCuts = 2;
           72  + int _ = 3;
           73  +END
           74  +CASE(1)
           75  + int eelLengths_[] = {5, 5, 5, 5};
           76  +   vector <int> eelLengths(eelLengths_, eelLengths_+sizeof(eelLengths_)/sizeof(*eelLengths_));
           77  + int maxCuts = 2;
           78  + int _ = 0;
           79  +END
           80  +CASE(2)
           81  + int eelLengths_[] = {34, 10, 48};
           82  +   vector <int> eelLengths(eelLengths_, eelLengths_+sizeof(eelLengths_)/sizeof(*eelLengths_));
           83  + int maxCuts = 4;
           84  + int _ = 5;
           85  +END
           86  +CASE(3)
           87  + int eelLengths_[] = {30, 50, 30, 50};
           88  +   vector <int> eelLengths(eelLengths_, eelLengths_+sizeof(eelLengths_)/sizeof(*eelLengths_));
           89  + int maxCuts = 350;
           90  + int _ = 16;
           91  +END
           92  +/*
           93  +CASE(4)
           94  + int eelLengths_[] = ;
           95  +   vector <int> eelLengths(eelLengths_, eelLengths_+sizeof(eelLengths_)/sizeof(*eelLengths_));
           96  + int maxCuts = ;
           97  + int _ = ;
           98  +END
           99  +CASE(5)
          100  + int eelLengths_[] = ;
          101  +   vector <int> eelLengths(eelLengths_, eelLengths_+sizeof(eelLengths_)/sizeof(*eelLengths_));
          102  + int maxCuts = ;
          103  + int _ = ;
          104  +END
          105  +*/
          106  +}
          107  +// END CUT HERE

Added SRM/528/1B.cpp version [e3b7dabae0461c08]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <cstring>
           18  +#ifdef __GNUC__
           19  +#include <ext/hash_map>
           20  +#define unordered_map __gnu_cxx::hash_map
           21  +#else
           22  +#include <unordered_map>
           23  +#endif
           24  +using namespace std;
           25  +typedef long long LL;
           26  +typedef complex<double> CMP;
           27  +
           28  +template<typename T>
           29  +struct DP2x
           30  +{
           31  + const int N1, N2;
           32  + vector<T> data;
           33  + DP2x(int, int N2, const T& t = T())
           34  +  : N1(2), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(1<<26)); }
           35  + T& operator()(int i1, int i2)
           36  +  { i1&=1; return data[ (i1*N2)+i2 ]; }
           37  + void swap(DP2x& rhs)
           38  +  { data.swap(rhs.data); }
           39  +};
           40  +
           41  +class SPartition { public:
           42  + long long getCount(string s)
           43  + {
           44  +  if( s.size()%2 != 0 )
           45  +   return 0;
           46  +
           47  +  int N = s.size()/2;
           48  +  DP2x<LL> dp(s.size()+1, 1<<N);
           49  +  for(int i=s.size(); i>=0; --i)
           50  +   for(int bits=0,ni=min(N,i); bits<(1<<ni); ++bits)
           51  +   {
           52  +    if( i == s.size() )
           53  +     dp(i,bits) = (bits==0 ? 1 : 0);
           54  +    else {
           55  +     if( bits == 0 ) {
           56  +      dp(i, bits) = dp(i+1, 1) * 2;
           57  +     } else {
           58  +      int iMax = 0;
           59  +      while( (2<<iMax) <= bits )
           60  +       ++iMax;
           61  +      int oldb = s[i-1-iMax];
           62  +      int newb = s[i];
           63  +      LL tot = 0;
           64  +      if( oldb == newb )
           65  +       tot += dp(i+1, (bits &~ (1<<iMax))<<1);
           66  +      if( (bits<<1 | 1) < (1<<N) )
           67  +       tot += dp(i+1, bits<<1 | 1);
           68  +      dp(i,bits) = tot;
           69  +     }
           70  +    }
           71  +   }
           72  +  return dp(0, 0);
           73  + }
           74  +};
           75  +
           76  +// BEGIN CUT HERE
           77  +#include <ctime>
           78  +double start_time; string timer()
           79  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           80  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           81  + { os << "{ ";
           82  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           83  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           84  +void verify_case(const long long& Expected, const long long& Received) {
           85  + bool ok = (Expected == Received);
           86  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           87  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           88  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           89  +#define END  verify_case(_, SPartition().getCount(s));}
           90  +int main(){
           91  +
           92  +CASE(0)
           93  + string s = "oxox";
           94  + long long _ = 2LL;
           95  +END
           96  +CASE(1)
           97  + string s = "oooxxx";
           98  + long long _ = 0LL;
           99  +END
          100  +CASE(2)
          101  + string s = "xoxxox";
          102  + long long _ = 4LL;
          103  +END
          104  +CASE(3)
          105  + string s = "xo";
          106  + long long _ = 0LL;
          107  +END
          108  +CASE(4)
          109  + string s = "ooooxoox";
          110  + long long _ = 8LL;
          111  +END
          112  +CASE(5)
          113  + string s = "ooxxoxox";
          114  + long long _ = 8LL;
          115  +END
          116  +CASE(6)
          117  + string s = "oxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox";
          118  + long long _ = -1LL;
          119  +END
          120  +/*
          121  +CASE(7)
          122  + string s = ;
          123  + long long _ = LL;
          124  +END
          125  +*/
          126  +}
          127  +// END CUT HERE

Added SRM/528/1C.cpp version [db458a8bf7c0ef4d]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <cstring>
           18  +#ifdef __GNUC__
           19  +#include <ext/hash_map>
           20  +#define unordered_map __gnu_cxx::hash_map
           21  +#else
           22  +#include <unordered_map>
           23  +#endif
           24  +using namespace std;
           25  +typedef long long LL;
           26  +typedef complex<double> CMP;
           27  +
           28  +template<typename T>
           29  +struct DP2x
           30  +{
           31  + const int N1, N2;
           32  + vector<T> data;
           33  + DP2x(int, int N2, const T& t = T())
           34  +  : N1(2), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(1<<26)); }
           35  + T& operator()(int i1, int i2)
           36  +  { i1&=1; return data[ (i1*N2)+i2 ]; }
           37  + void swap(DP2x& rhs)
           38  +  { data.swap(rhs.data); }
           39  +};
           40  +
           41  +class ColorfulCookie { public:
           42  + int getMaximum(vector <int> cookies, int P1, int P2)
           43  + {
           44  +  int L = 0;
           45  +  int R = accumulate(cookies.begin(), cookies.end(), 0) / (P1+P2) + 1;
           46  +  while( R-L > 1 ) { // [L, R)
           47  +   int C = (L+R) / 2;
           48  +   (possible(cookies, P1, P2, C) ? L : R) = C;
           49  +  }
           50  +  return L * (P1+P2);
           51  + }
           52  +
           53  + bool possible(const vector<int>& C, int P1, int P2, int Times)
           54  + {
           55  +  DP2x<int> maxP2forP1(C.size()+1, Times+1, -1);
           56  +  maxP2forP1(0,0) = 0;
           57  +  for(int i=0; i<C.size(); ++i)
           58  +   for(int n=0; n<=Times; ++n) {
           59  +    maxP2forP1(i+1,n) = maxP2forP1(i,n);
           60  +    for(int a=0; a<=n; ++a) {
           61  +     if( n-a>=0 && maxP2forP1(i,n-a)>=0 && C[i]-a*P1>=0 )
           62  +      maxP2forP1(i+1,n) = max(maxP2forP1(i+1,n),
           63  +       maxP2forP1(i,n-a) + min(Times-a,(C[i]-a*P1)/P2)
           64  +      );
           65  +    }
           66  +   }
           67  +  return maxP2forP1(C.size(), Times) >= Times;
           68  + }
           69  +};
           70  +
           71  +// BEGIN CUT HERE
           72  +#include <ctime>
           73  +double start_time; string timer()
           74  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           75  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           76  + { os << "{ ";
           77  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           78  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           79  +void verify_case(const int& Expected, const int& Received) {
           80  + bool ok = (Expected == Received);
           81  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           82  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           83  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           84  +#define END  verify_case(_, ColorfulCookie().getMaximum(cookies, P1, P2));}
           85  +int main(){
           86  +
           87  +CASE(0)
           88  + int cookies_[] = {100, 100};
           89  +   vector <int> cookies(cookies_, cookies_+sizeof(cookies_)/sizeof(*cookies_));
           90  + int P1 = 50;
           91  + int P2 = 50;
           92  + int _ = 200;
           93  +END
           94  +CASE(1)
           95  + int cookies_[] = {50, 250, 50};
           96  +   vector <int> cookies(cookies_, cookies_+sizeof(cookies_)/sizeof(*cookies_));
           97  + int P1 = 50;
           98  + int P2 = 100;
           99  + int _ = 300;
          100  +END
          101  +CASE(2)
          102  + int cookies_[] = {2000};
          103  +   vector <int> cookies(cookies_, cookies_+sizeof(cookies_)/sizeof(*cookies_));
          104  + int P1 = 100;
          105  + int P2 = 200;
          106  + int _ = 0;
          107  +END
          108  +CASE(3)
          109  + int cookies_[] = {123, 456, 789, 555};
          110  +   vector <int> cookies(cookies_, cookies_+sizeof(cookies_)/sizeof(*cookies_));
          111  + int P1 = 58;
          112  + int P2 = 158;
          113  + int _ = 1728;
          114  +END
          115  +/*
          116  +CASE(4)
          117  + int cookies_[] = ;
          118  +   vector <int> cookies(cookies_, cookies_+sizeof(cookies_)/sizeof(*cookies_));
          119  + int P1 = ;
          120  + int P2 = ;
          121  + int _ = ;
          122  +END
          123  +CASE(5)
          124  + int cookies_[] = ;
          125  +   vector <int> cookies(cookies_, cookies_+sizeof(cookies_)/sizeof(*cookies_));
          126  + int P1 = ;
          127  + int P2 = ;
          128  + int _ = ;
          129  +END
          130  +*/
          131  +}
          132  +// END CUT HERE

Modified lib/typical/dp.cpp from [ae16b2462960bb78] to [feb5fdb1e50b8e31].

     8      8     : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(1<<26)); }
     9      9    T& operator()(int i1, int i2)
    10     10     { return data[ (i1*N2)+i2 ]; }
    11     11    void swap(DP2& rhs)
    12     12     { data.swap(rhs.data); }
    13     13   };
    14     14   
    15         -// Tested: Codeforces #13 C
           15  +// Tested: Codeforces #13 C, SRM 528 Lv2
    16     16   template<typename T>
    17     17   struct DP2x
    18     18   {
    19     19    const int N1, N2;
    20     20    vector<T> data;
    21     21    DP2x(int, int N2, const T& t = T())
    22     22     : N1(2), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(1<<26)); }