ba35b3a9cf 2011-06-25 kinaba: #include <iostream> ba35b3a9cf 2011-06-25 kinaba: #include <sstream> ba35b3a9cf 2011-06-25 kinaba: #include <iomanip> ba35b3a9cf 2011-06-25 kinaba: #include <vector> ba35b3a9cf 2011-06-25 kinaba: #include <string> ba35b3a9cf 2011-06-25 kinaba: #include <map> ba35b3a9cf 2011-06-25 kinaba: #include <set> ba35b3a9cf 2011-06-25 kinaba: #include <algorithm> ba35b3a9cf 2011-06-25 kinaba: #include <numeric> ba35b3a9cf 2011-06-25 kinaba: #include <iterator> ba35b3a9cf 2011-06-25 kinaba: #include <functional> ba35b3a9cf 2011-06-25 kinaba: #include <complex> ba35b3a9cf 2011-06-25 kinaba: #include <queue> ba35b3a9cf 2011-06-25 kinaba: #include <stack> ba35b3a9cf 2011-06-25 kinaba: #include <cmath> ba35b3a9cf 2011-06-25 kinaba: #include <cassert> ba35b3a9cf 2011-06-25 kinaba: #include <cstring> ba35b3a9cf 2011-06-25 kinaba: using namespace std; ba35b3a9cf 2011-06-25 kinaba: typedef long long LL; ba35b3a9cf 2011-06-25 kinaba: typedef complex<double> CMP; ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: class IPv444 { public: ba35b3a9cf 2011-06-25 kinaba: struct Request ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: int x[4]; ba35b3a9cf 2011-06-25 kinaba: int y[4]; ba35b3a9cf 2011-06-25 kinaba: LL p; ba35b3a9cf 2011-06-25 kinaba: Request(const string& r, LL p) : p(p) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: for(int d=0,s=0; d<4; ++d) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: int e=s+1; ba35b3a9cf 2011-06-25 kinaba: while( e<r.size() && r[e]!='.' ) ba35b3a9cf 2011-06-25 kinaba: ++e; ba35b3a9cf 2011-06-25 kinaba: string num(r.begin()+s, r.begin()+e); ba35b3a9cf 2011-06-25 kinaba: if( num == "*" ) { ba35b3a9cf 2011-06-25 kinaba: x[d] = 0; ba35b3a9cf 2011-06-25 kinaba: y[d] = 1000; ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: else { ba35b3a9cf 2011-06-25 kinaba: x[d] = atoi(num.c_str()); ba35b3a9cf 2011-06-25 kinaba: y[d] = x[d]+1; ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: s = e+1; ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: bool operator<(const Request& rhs) const ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: if( p != rhs.p ) ba35b3a9cf 2011-06-25 kinaba: return p < rhs.p; ba35b3a9cf 2011-06-25 kinaba: for(int d=0; d<4; ++d) ba35b3a9cf 2011-06-25 kinaba: if( x[d] != rhs.x[d] ) ba35b3a9cf 2011-06-25 kinaba: return x[d] < rhs.x[d]; ba35b3a9cf 2011-06-25 kinaba: return false; ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: }; ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: long long getMaximumMoney(vector <string> request, vector <int> price) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: vector<Request> req; ba35b3a9cf 2011-06-25 kinaba: for(size_t i=0; i<request.size(); ++i) ba35b3a9cf 2011-06-25 kinaba: req.push_back( Request(request[i], price[i]) ); ba35b3a9cf 2011-06-25 kinaba: sort(req.rbegin(), req.rend()); ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: static const int MID = 2; ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: vector<int> sig[4]; ba35b3a9cf 2011-06-25 kinaba: for(int d=0; d<MID; ++d) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: set<int> sigs; ba35b3a9cf 2011-06-25 kinaba: for(int i=0; i<req.size(); ++i) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: sigs.insert(req[i].x[d]); ba35b3a9cf 2011-06-25 kinaba: sigs.insert(req[i].y[d]); ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: sig[d].assign(sigs.begin(), sigs.end()); ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: LL sum = 0; ba35b3a9cf 2011-06-25 kinaba: int i[4]; ba35b3a9cf 2011-06-25 kinaba: for(i[0]=0; i[0]+1<sig[0].size(); ++i[0]) ba35b3a9cf 2011-06-25 kinaba: for(i[1]=0; i[1]+1<sig[1].size(); ++i[1]) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: for(int d=MID; d<4; ++d) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: set<int> sigs; ba35b3a9cf 2011-06-25 kinaba: for(int k=0; k<req.size(); ++k) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: bool dame = false; ba35b3a9cf 2011-06-25 kinaba: for(int dd=0; dd<MID; ++dd) ba35b3a9cf 2011-06-25 kinaba: if( !(req[k].x[dd]<=sig[dd][i[dd]] && sig[dd][i[dd]+1]<=req[k].y[dd]) ) ba35b3a9cf 2011-06-25 kinaba: dame = true; ba35b3a9cf 2011-06-25 kinaba: if(!dame) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: sigs.insert(req[k].x[d]); ba35b3a9cf 2011-06-25 kinaba: sigs.insert(req[k].y[d]); ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: sig[d].assign(sigs.begin(), sigs.end()); ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: for(i[2]=0; i[2]+1<sig[2].size(); ++i[2]) ba35b3a9cf 2011-06-25 kinaba: for(i[3]=0; i[3]+1<sig[3].size(); ++i[3]) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: LL p = 0; ba35b3a9cf 2011-06-25 kinaba: for(int k=0; k<req.size(); ++k) ba35b3a9cf 2011-06-25 kinaba: { ba35b3a9cf 2011-06-25 kinaba: bool dame = false; ba35b3a9cf 2011-06-25 kinaba: for(int d=0; d<4; ++d) ba35b3a9cf 2011-06-25 kinaba: if( !(req[k].x[d]<=sig[d][i[d]] && sig[d][i[d]+1]<=req[k].y[d]) ) ba35b3a9cf 2011-06-25 kinaba: dame = true; ba35b3a9cf 2011-06-25 kinaba: if(!dame) ba35b3a9cf 2011-06-25 kinaba: {p = req[k].p; break;} ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: LL a = p; ba35b3a9cf 2011-06-25 kinaba: for(int dd=0; dd<4; ++dd) ba35b3a9cf 2011-06-25 kinaba: a *= sig[dd][i[dd]+1] - sig[dd][i[dd]]; ba35b3a9cf 2011-06-25 kinaba: sum += a; ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: return sum; ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: }; ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: // BEGIN CUT HERE ba35b3a9cf 2011-06-25 kinaba: #include <ctime> ba35b3a9cf 2011-06-25 kinaba: double start_time; string timer() ba35b3a9cf 2011-06-25 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } ba35b3a9cf 2011-06-25 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) ba35b3a9cf 2011-06-25 kinaba: { os << "{ "; ba35b3a9cf 2011-06-25 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) ba35b3a9cf 2011-06-25 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } ba35b3a9cf 2011-06-25 kinaba: void verify_case(const long long& Expected, const long long& Received) { ba35b3a9cf 2011-06-25 kinaba: bool ok = (Expected == Received); ba35b3a9cf 2011-06-25 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; ba35b3a9cf 2011-06-25 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } ba35b3a9cf 2011-06-25 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); ba35b3a9cf 2011-06-25 kinaba: #define END verify_case(_, IPv444().getMaximumMoney(request, price));} ba35b3a9cf 2011-06-25 kinaba: int main(){ ba35b3a9cf 2011-06-25 kinaba: ba35b3a9cf 2011-06-25 kinaba: CASE(0) ba35b3a9cf 2011-06-25 kinaba: string request_[] = {"66.37.210.86"}; ba35b3a9cf 2011-06-25 kinaba: vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_)); ba35b3a9cf 2011-06-25 kinaba: int price_[] = {47}; ba35b3a9cf 2011-06-25 kinaba: vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); ba35b3a9cf 2011-06-25 kinaba: long long _ = 47LL; ba35b3a9cf 2011-06-25 kinaba: END ba35b3a9cf 2011-06-25 kinaba: CASE(1) ba35b3a9cf 2011-06-25 kinaba: string request_[] = {"0.0.0.*", "0.0.0.3", "0.0.0.5"}; ba35b3a9cf 2011-06-25 kinaba: vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_)); ba35b3a9cf 2011-06-25 kinaba: int price_[] = {1, 3, 9}; ba35b3a9cf 2011-06-25 kinaba: vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); ba35b3a9cf 2011-06-25 kinaba: long long _ = 1010LL; ba35b3a9cf 2011-06-25 kinaba: END ba35b3a9cf 2011-06-25 kinaba: CASE(2) ba35b3a9cf 2011-06-25 kinaba: string request_[] = {"*.*.*.*", "123.456.789.0", "434.434.434.434", "999.*.999.*"}; ba35b3a9cf 2011-06-25 kinaba: vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_)); ba35b3a9cf 2011-06-25 kinaba: int price_[] = {1, 5, 3, 6}; ba35b3a9cf 2011-06-25 kinaba: vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); ba35b3a9cf 2011-06-25 kinaba: long long _ = 1000005000006LL; ba35b3a9cf 2011-06-25 kinaba: END ba35b3a9cf 2011-06-25 kinaba: CASE(3) ba35b3a9cf 2011-06-25 kinaba: string request_[] = {"*.*.999.999", "888.888.999.*", "888.888.*.999", "777.777.777.777", "777.*.*.777"}; ba35b3a9cf 2011-06-25 kinaba: vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_)); ba35b3a9cf 2011-06-25 kinaba: int price_[] = {19, 33, 42, 777, 7}; ba35b3a9cf 2011-06-25 kinaba: vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); ba35b3a9cf 2011-06-25 kinaba: long long _ = 26075718LL; ba35b3a9cf 2011-06-25 kinaba: END ba35b3a9cf 2011-06-25 kinaba: CASE(4) ba35b3a9cf 2011-06-25 kinaba: string request_[] = {"127.0.0.1", "*.0.0.*", "*.*.255.255", "192.68.*.*"}; ba35b3a9cf 2011-06-25 kinaba: vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_)); ba35b3a9cf 2011-06-25 kinaba: int price_[] = {999999, 629851, 294016, 438090}; ba35b3a9cf 2011-06-25 kinaba: vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); ba35b3a9cf 2011-06-25 kinaba: long long _ = 1361957076132LL; ba35b3a9cf 2011-06-25 kinaba: END ba35b3a9cf 2011-06-25 kinaba: CASE(5) ba35b3a9cf 2011-06-25 kinaba: string request_[] = { ba35b3a9cf 2011-06-25 kinaba: "1.1.1.1", ba35b3a9cf 2011-06-25 kinaba: "3.3.3.3", ba35b3a9cf 2011-06-25 kinaba: "5.5.5.5", ba35b3a9cf 2011-06-25 kinaba: "7.7.7.7", ba35b3a9cf 2011-06-25 kinaba: "9.9.9.9", ba35b3a9cf 2011-06-25 kinaba: "11.11.11.11", ba35b3a9cf 2011-06-25 kinaba: "13.13.13.13", ba35b3a9cf 2011-06-25 kinaba: "15.15.15.15", ba35b3a9cf 2011-06-25 kinaba: "17.17.17.17", ba35b3a9cf 2011-06-25 kinaba: "19.19.19.19", ba35b3a9cf 2011-06-25 kinaba: "21.21.21.21", ba35b3a9cf 2011-06-25 kinaba: "23.23.23.23", ba35b3a9cf 2011-06-25 kinaba: "25.25.25.25", ba35b3a9cf 2011-06-25 kinaba: "27.27.27.27", ba35b3a9cf 2011-06-25 kinaba: "29.29.29.29", ba35b3a9cf 2011-06-25 kinaba: "31.31.31.31", ba35b3a9cf 2011-06-25 kinaba: "33.33.33.33", ba35b3a9cf 2011-06-25 kinaba: "35.35.35.35", ba35b3a9cf 2011-06-25 kinaba: "37.37.37.37", ba35b3a9cf 2011-06-25 kinaba: "39.39.39.39", ba35b3a9cf 2011-06-25 kinaba: "41.41.41.41", ba35b3a9cf 2011-06-25 kinaba: "43.43.43.43", ba35b3a9cf 2011-06-25 kinaba: "45.45.45.45", ba35b3a9cf 2011-06-25 kinaba: "47.47.47.47", ba35b3a9cf 2011-06-25 kinaba: "49.49.49.49", ba35b3a9cf 2011-06-25 kinaba: "51.51.51.51", ba35b3a9cf 2011-06-25 kinaba: "53.53.53.53", ba35b3a9cf 2011-06-25 kinaba: "55.55.55.55", ba35b3a9cf 2011-06-25 kinaba: "57.57.57.57", ba35b3a9cf 2011-06-25 kinaba: "59.59.59.59", ba35b3a9cf 2011-06-25 kinaba: }; ba35b3a9cf 2011-06-25 kinaba: vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_)); ba35b3a9cf 2011-06-25 kinaba: int price_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; ba35b3a9cf 2011-06-25 kinaba: vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); ba35b3a9cf 2011-06-25 kinaba: long long _ = -1LL; ba35b3a9cf 2011-06-25 kinaba: END ba35b3a9cf 2011-06-25 kinaba: /* ba35b3a9cf 2011-06-25 kinaba: CASE(6) ba35b3a9cf 2011-06-25 kinaba: string request_[] = ; ba35b3a9cf 2011-06-25 kinaba: vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_)); ba35b3a9cf 2011-06-25 kinaba: int price_[] = ; ba35b3a9cf 2011-06-25 kinaba: vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); ba35b3a9cf 2011-06-25 kinaba: long long _ = LL; ba35b3a9cf 2011-06-25 kinaba: END ba35b3a9cf 2011-06-25 kinaba: */ ba35b3a9cf 2011-06-25 kinaba: } ba35b3a9cf 2011-06-25 kinaba: // END CUT HERE