Overview
| SHA1 Hash: | 7fcb6bef04b180f31d26bd37abd9afb8400ade7c |
|---|---|
| Date: | 2014-01-06 14:56:46 |
| User: | kinaba |
| Comment: | 601 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added SRM/601-U/1A.cpp version [08c08afc02a9f35f]
> 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 <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class WinterAndPresents { public: > 23 long long getNumber(vector <int> apple, vector <int> orange) > 24 { > 25 const int N = apple.size(); > 26 int Xmax = 0x3fffffff; > 27 for(int i=0; i<N; ++i) > 28 Xmax = min(Xmax, apple[i]+orange[i]); > 29 > 30 LL total = 0; > 31 for(int X=1; X<=Xmax; ++X) { > 32 int am=0, aM=0; > 33 for(int i=0; i<N; ++i) { > 34 am += (X<=orange[i] ? 0 : X-orange[i]); > 35 aM += (X<=apple[i] ? X : apple[i]); > 36 } > 37 total += (aM-am+1); > 38 } > 39 return total; > 40 } > 41 }; > 42 > 43 // BEGIN CUT HERE > 44 #include <ctime> > 45 double start_time; string timer() > 46 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 47 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 48 { os << "{ "; > 49 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 50 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 51 void verify_case(const long long& Expected, const long long& Received) { > 52 bool ok = (Expected == Received); > 53 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 54 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 55 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 56 #define END verify_case(_, WinterAndPresents().getNumber(apple, orange));} > 57 int main(){ > 58 > 59 CASE(0) > 60 int apple_[] = {1}; > 61 vector <int> apple(apple_, apple_+sizeof(apple_)/sizeof(*apple_)); > 62 int orange_[] = {1}; > 63 vector <int> orange(orange_, orange_+sizeof(orange_)/sizeof(*orange_)) > 64 long long _ = 3LL; > 65 END > 66 CASE(1) > 67 int apple_[] = {1, 2, 0, 3}; > 68 vector <int> apple(apple_, apple_+sizeof(apple_)/sizeof(*apple_)); > 69 int orange_[] = {4, 5, 0, 6}; > 70 vector <int> orange(orange_, orange_+sizeof(orange_)/sizeof(*orange_)) > 71 long long _ = 0LL; > 72 END > 73 CASE(2) > 74 int apple_[] = {2, 2, 2}; > 75 vector <int> apple(apple_, apple_+sizeof(apple_)/sizeof(*apple_)); > 76 int orange_[] = {2, 2, 2}; > 77 vector <int> orange(orange_, orange_+sizeof(orange_)/sizeof(*orange_)) > 78 long long _ = 16LL; > 79 END > 80 CASE(3) > 81 int apple_[] = {7, 4, 5}; > 82 vector <int> apple(apple_, apple_+sizeof(apple_)/sizeof(*apple_)); > 83 int orange_[] = {1, 10, 2}; > 84 vector <int> orange(orange_, orange_+sizeof(orange_)/sizeof(*orange_)) > 85 long long _ = 46LL; > 86 END > 87 CASE(4) > 88 int apple_[] = {1000000}; > 89 vector <int> apple(apple_, apple_+sizeof(apple_)/sizeof(*apple_)); > 90 int orange_[] = {1000000}; > 91 vector <int> orange(orange_, orange_+sizeof(orange_)/sizeof(*orange_)) > 92 long long _ = 1000002000000LL; > 93 END > 94 CASE(5) > 95 int apple_[] = {1000000,1000000,1000000,1000000,1000000,1000000,1000000, > 96 vector <int> apple(apple_, apple_+sizeof(apple_)/sizeof(*apple_)); > 97 int orange_[] = {1000000,1000000,1000000,1000000,1000000,1000000,1000000 > 98 vector <int> orange(orange_, orange_+sizeof(orange_)/sizeof(*orange_)) > 99 long long _ = -1LL; > 100 END > 101 /* > 102 CASE(6) > 103 int apple_[] = ; > 104 vector <int> apple(apple_, apple_+sizeof(apple_)/sizeof(*apple_)); > 105 int orange_[] = ; > 106 vector <int> orange(orange_, orange_+sizeof(orange_)/sizeof(*orange_)) > 107 long long _ = LL; > 108 END > 109 */ > 110 } > 111 // END CUT HERE
Added SRM/601-U/1B.cpp version [8a76bc3da2574066]
> 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 <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 static const unsigned MODVAL = 1000000007; > 23 struct mint > 24 { > 25 unsigned val; > 26 mint():val(0){} > 27 mint(int x):val(x%MODVAL) {} > 28 mint(unsigned x):val(x%MODVAL) {} > 29 mint(LL x):val(x%MODVAL) {} > 30 }; > 31 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } > 32 mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } > 33 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } > 34 mint operator+(mint x, mint y) { return x+=y; } > 35 mint operator-(mint x, mint y) { return x-=y; } > 36 mint operator*(mint x, mint y) { return x*=y; } > 37 > 38 template<typename T> > 39 struct DP3x > 40 { > 41 int N1, N2, N3; > 42 vector<T> data; > 43 DP3x(int, int N2, int N3, const T& t = T()) > 44 : N1(2), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()* > 45 T& operator()(int i1, int i2, int i3) > 46 { i1&=1; return data[ ((i1*N2)+i2)*N3+i3 ]; } > 47 void swap(DP3x& rhs) > 48 { data.swap(rhs.data); } > 49 }; > 50 > 51 class WinterAndSnowmen { public: > 52 int getNumber(int N, int M) > 53 { > 54 const int MAX = max(N,M); > 55 mint total; > 56 for(int B=10; B>=0; --B) > 57 { > 58 int HH = 2048>>(B+1); > 59 DP3x<mint> dp(MAX+1, HH, 4); > 60 dp(0,0,0) = 1; > 61 for(int k=1; k<=MAX; ++k) { > 62 for(int high=0; high<HH; ++high) > 63 for(int key=0; key<4; ++key) > 64 dp(k, high, key) = dp(k-1, high, > 65 > 66 for(int high=0; high<HH; ++high) > 67 for(int key=0; key<4; ++key) { > 68 int kh = k>>(B+1); > 69 int kk = (k>>B)&1; > 70 if(k<=N) > 71 dp(k, high^kh, key^(kk<< > 72 if(k<=M) > 73 dp(k, high^kh, key^kk) + > 74 } > 75 } > 76 total += dp(MAX, 0, 1); > 77 } > 78 return total.val; > 79 } > 80 }; > 81 > 82 // BEGIN CUT HERE > 83 #include <ctime> > 84 double start_time; string timer() > 85 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 86 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 87 { os << "{ "; > 88 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 89 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 90 void verify_case(const int& Expected, const int& Received) { > 91 bool ok = (Expected == Received); > 92 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 93 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 94 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 95 #define END verify_case(_, WinterAndSnowmen().getNumber(N, M));} > 96 int main(){ > 97 > 98 CASE(0) > 99 int N = 2; > 100 int M = 2; > 101 int _ = 4; > 102 END > 103 CASE(1) > 104 int N = 1; > 105 int M = 1; > 106 int _ = 1; > 107 END > 108 CASE(2) > 109 int N = 3; > 110 int M = 5; > 111 int _ = 74; > 112 END > 113 CASE(3) > 114 int N = 7; > 115 int M = 4; > 116 int _ = 216; > 117 END > 118 CASE(4) > 119 int N = 47; > 120 int M = 74; > 121 int _ = 962557390; > 122 END > 123 CASE(5) > 124 int N = 2000; > 125 int M = 2000; > 126 int _ = -1; > 127 END > 128 /* > 129 CASE(6) > 130 int N = ; > 131 int M = ; > 132 int _ = ; > 133 END > 134 */ > 135 } > 136 // END CUT HERE