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

Added SRM/532-U/1A.cpp version [f4151cb9a6769ef3]

            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 DengklekMakingChains { public:
           29  + int maxBeauty(vector <string> chains)
           30  + {
           31  +  int best = 0;
           32  +  for(int C=0; C<chains.size(); ++C) {
           33  +   best = max(best, single(chains[C]));
           34  +  }
           35  +
           36  +  for(int L=0; L<chains.size(); ++L)
           37  +  {
           38  +   int vl = c__( string(chains[L].rbegin(), chains[L].rend()) );
           39  +   for(int R=0; R<chains.size(); ++R) if( L != R )
           40  +   {
           41  +    int v = vl + c__(chains[R]);
           42  +    for(int C=0; C<chains.size(); ++C) if(C!=L && C!=R)
           43  +     v += all(chains[C]);
           44  +    best = max(best, v);
           45  +   }
           46  +  }
           47  +  return best;
           48  + }
           49  +
           50  + int single(const string& s)
           51  + {
           52  +  int best = 0;
           53  +  for(int i=0; i<3; ++i)
           54  +   for(int k=i+1; k<=3; ++k) {
           55  +    int v = 0;
           56  +    for(int a=i; a<k; ++a)
           57  +     if(s[a]!='.')
           58  +      v += s[a]-'0';
           59  +     else
           60  +      goto next;
           61  +    best = max(best, v);
           62  +   next:;
           63  +   }
           64  +  return best;
           65  + }
           66  + int all(const string& s)
           67  + {
           68  +  int v = 0;
           69  +  for(int a=0; a<3; ++a)
           70  +   if(s[a]!='.')
           71  +    v += s[a]-'0';
           72  +   else
           73  +    return 0;
           74  +  return v;
           75  + }
           76  + int c__(const string& s)
           77  + {
           78  +  int v = 0;
           79  +  for(int a=0; a<3; ++a)
           80  +   if(s[a]!='.')
           81  +    v += s[a]-'0';
           82  +   else
           83  +    return v;
           84  +  return v;
           85  + }
           86  +};
           87  +
           88  +// BEGIN CUT HERE
           89  +#include <ctime>
           90  +double start_time; string timer()
           91  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           92  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           93  + { os << "{ ";
           94  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           95  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           96  +void verify_case(const int& Expected, const int& Received) {
           97  + bool ok = (Expected == Received);
           98  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           99  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          100  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          101  +#define END  verify_case(_, DengklekMakingChains().maxBeauty(chains));}
          102  +int main(){
          103  +
          104  +CASE(0)
          105  + string chains_[] = {".15", "7..", "402", "..3"};
          106  +   vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_));
          107  + int _ = 19;
          108  + // .15 402 7..
          109  +END
          110  +CASE(1)
          111  + string chains_[] = {"..1", "7..", "567", "24.", "8..", "234"};
          112  +   vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_));
          113  + int _ = 36;
          114  + // ..1 567 234 8..
          115  +END
          116  +CASE(2)
          117  + string chains_[] = {"...", "..."};
          118  +   vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_));
          119  + int _ = 0;
          120  +END
          121  +CASE(3)
          122  + string chains_[] = {"16.", "9.8", ".24", "52.", "3.1", "532", "4.4", "111"};
          123  +   vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_));
          124  + int _ = 28;
          125  + // .24 532 111 9.8
          126  + // or
          127  + // 9.8 532 111 16.
          128  +END
          129  +CASE(4)
          130  + string chains_[] = {"..1", "3..", "2..", ".7."};
          131  +   vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_));
          132  + int _ = 7;
          133  + // .7.
          134  +END
          135  +CASE(5)
          136  + string chains_[] = {"412", "..7", ".58", "7.8", "32.", "6..", "351", "3.9", "985", "...", ".46"};
          137  +   vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_));
          138  + int _ = 58;
          139  + // .58 412 351 985 7.8
          140  +END
          141  +CASE(6)
          142  + string chains_[] = {"9..", "..9"};
          143  +   vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_));
          144  + int _ = 18;
          145  +END
          146  +CASE(7)
          147  + string chains_[] = {"..1"};
          148  +   vector <string> chains(chains_, chains_+sizeof(chains_)/sizeof(*chains_));
          149  + int _ = 1;
          150  +END
          151  +}
          152  +// END CUT HERE

Added SRM/532-U/1B.cpp version [6d39c5c3460aa153]

            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  +static const int MODVAL = 1000000007;
           29  +struct mint
           30  +{
           31  + int val;
           32  + mint():val(0){}
           33  + mint(int    x):val(x%MODVAL) {} // x>=0
           34  + mint(size_t x):val(x%MODVAL) {} // x>=0
           35  + mint(LL     x):val(x%MODVAL) {} // x>=0
           36  +};
           37  +mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
           38  +mint operator+(mint x, mint y) { return x+=y; }
           39  +
           40  +template<typename T>
           41  +struct DP4
           42  +{
           43  + int N1, N2, N3, N4;
           44  + vector<T> data;
           45  + DP4(int N1, int N2, int N3, int N4, const T& t = T())
           46  +  : N1(N1), N2(N2), N3(N3), N4(N4), data(N1*N2*N3*N4, t) { assert(data.size()*sizeof(T)<(1<<26)); }
           47  + T& operator()(int i1, int i2, int i3, int i4)
           48  +  { return data[ (((i1*N2)+i2)*N3+i3)*N4+i4 ]; }
           49  + void swap(DP4& rhs)
           50  +  { data.swap(rhs.data); }
           51  +};
           52  +
           53  +class DengklekBuildingRoads { public:
           54  + int numWays(int N, int M, int K)
           55  + {
           56  +  DP4<mint> dp(N, M+1, 1<<K+1, K);
           57  +  for(int a=N-1; a>=0; --a)
           58  +  for(int e=0; e<=M; ++e)
           59  +  for(int mask=0; mask<(1<<K+1); ++mask)
           60  +  for(int b=K-1; b>=0; --b)
           61  +  {
           62  +   mint v = 0;
           63  +   // draw edge
           64  +   if(e && a+b+1<N)
           65  +    v += dp(a, e-1, mask^1^(1<<b+1), b);
           66  +
           67  +   // no edge
           68  +   if(b+1<K)
           69  +    v += dp(a, e, mask, b+1);
           70  +   else {
           71  +    if(a+1<N) {
           72  +     if( (mask&1)==0 )
           73  +      v += dp(a+1,e,mask>>1,0);
           74  +    } else {
           75  +     if( mask==0 && e==0 )
           76  +      v += 1;
           77  +    }
           78  +   }
           79  +   dp(a,e,mask,b) = v;
           80  +  }
           81  +  return dp(0,M,0,0).val;
           82  + }
           83  +};
           84  +
           85  +// BEGIN CUT HERE
           86  +#include <ctime>
           87  +double start_time; string timer()
           88  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           89  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           90  + { os << "{ ";
           91  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           92  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           93  +void verify_case(const int& Expected, const int& Received) {
           94  + bool ok = (Expected == Received);
           95  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           96  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           97  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           98  +#define END  verify_case(_, DengklekBuildingRoads().numWays(N, M, K));}
           99  +int main(){
          100  +
          101  +CASE(0)
          102  + int N = 3;
          103  + int M = 4;
          104  + int K = 1;
          105  + int _ = 3;
          106  +END
          107  +CASE(1)
          108  + int N = 4;
          109  + int M = 3;
          110  + int K = 3;
          111  + int _ = 4;
          112  +END
          113  +CASE(2)
          114  + int N = 2;
          115  + int M = 1;
          116  + int K = 1;
          117  + int _ = 0;
          118  +END
          119  +CASE(3)
          120  + int N = 5;
          121  + int M = 0;
          122  + int K = 3;
          123  + int _ = 1;
          124  +END
          125  +CASE(4)
          126  + int N = 10;
          127  + int M = 20;
          128  + int K = 5;
          129  + int _ = 26964424;
          130  +END
          131  +CASE(5)
          132  + int N = 1;
          133  + int M = 0;
          134  + int K = 1;
          135  + int _ = 1;
          136  +END
          137  +CASE(6)
          138  + int N = 30;
          139  + int M = 30;
          140  + int K = 8;
          141  + int _ = -1;
          142  +END
          143  +
          144  +}
          145  +// END CUT HERE