Artifact Content
Not logged in

Artifact 7383f594e57587765acbda0a8473fe97ec79184b


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

class IPv444 { public:
	struct Request
	{
		int x[4];
		int y[4];
		LL p;
		Request(const string& r, LL p) : p(p)
		{
			for(int d=0,s=0; d<4; ++d)
			{
				int e=s+1;
				while( e<r.size() && r[e]!='.' )
					++e;
				string num(r.begin()+s, r.begin()+e);
				if( num == "*" ) {
					x[d] = 0;
					y[d] = 1000;
				}
				else {
					x[d] = atoi(num.c_str());
					y[d] = x[d]+1;
				}
				s = e+1;
			}
		}

		bool operator<(const Request& rhs) const
		{
			if( p != rhs.p )
				return p < rhs.p;
			for(int d=0; d<4; ++d)
				if( x[d] != rhs.x[d] )
					return x[d] < rhs.x[d];
			return false;
		}
	};

	long long getMaximumMoney(vector <string> request, vector <int> price) 
	{
		vector<Request> req;
		for(size_t i=0; i<request.size(); ++i)
			req.push_back( Request(request[i], price[i]) );
		sort(req.rbegin(), req.rend());

		static const int MID = 2;

		vector<int> sig[4];
		for(int d=0; d<MID; ++d)
		{
			set<int> sigs;
			for(int i=0; i<req.size(); ++i)
			{
				sigs.insert(req[i].x[d]);
				sigs.insert(req[i].y[d]);
			}
			sig[d].assign(sigs.begin(), sigs.end());
		}

		LL sum = 0;
		int i[4];
		for(i[0]=0; i[0]+1<sig[0].size(); ++i[0])
		for(i[1]=0; i[1]+1<sig[1].size(); ++i[1])
		{
			for(int d=MID; d<4; ++d)
			{
				set<int> sigs;
				for(int k=0; k<req.size(); ++k)
				{
					bool dame = false;
					for(int dd=0; dd<MID; ++dd)
						if( !(req[k].x[dd]<=sig[dd][i[dd]] && sig[dd][i[dd]+1]<=req[k].y[dd]) )
							dame = true;
					if(!dame)
					{
						sigs.insert(req[k].x[d]);
						sigs.insert(req[k].y[d]);
					}
				}
				sig[d].assign(sigs.begin(), sigs.end());
			}
			for(i[2]=0; i[2]+1<sig[2].size(); ++i[2])
			for(i[3]=0; i[3]+1<sig[3].size(); ++i[3])
			{
				LL p = 0;
				for(int k=0; k<req.size(); ++k)
				{
					bool dame = false;
					for(int d=0; d<4; ++d)
						if( !(req[k].x[d]<=sig[d][i[d]] && sig[d][i[d]+1]<=req[k].y[d]) )
							dame = true;
					if(!dame)
						{p = req[k].p; break;}
				}
				LL a = p;
				for(int dd=0; dd<4; ++dd)
					a *= sig[dd][i[dd]+1] - sig[dd][i[dd]];
				sum += a;
			}
		}
		return sum;
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const long long& Expected, const long long& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, IPv444().getMaximumMoney(request, price));}
int main(){

CASE(0)
	string request_[] = {"66.37.210.86"};
	  vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_)); 
	int price_[] = {47};
	  vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 
	long long _ = 47LL; 
END
CASE(1)
	string request_[] = {"0.0.0.*", "0.0.0.3", "0.0.0.5"};
	  vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_)); 
	int price_[] = {1, 3, 9};
	  vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 
	long long _ = 1010LL; 
END
CASE(2)
	string request_[] = {"*.*.*.*", "123.456.789.0", "434.434.434.434", "999.*.999.*"};
	  vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_)); 
	int price_[] = {1, 5, 3, 6};
	  vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 
	long long _ = 1000005000006LL; 
END
CASE(3)
	string request_[] = {"*.*.999.999", "888.888.999.*", "888.888.*.999", "777.777.777.777", "777.*.*.777"};
	  vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_)); 
	int price_[] = {19, 33, 42, 777, 7};
	  vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 
	long long _ = 26075718LL; 
END
CASE(4)
	string request_[] = {"127.0.0.1", "*.0.0.*", "*.*.255.255", "192.68.*.*"};
	  vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_)); 
	int price_[] = {999999, 629851, 294016, 438090};
	  vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 
	long long _ = 1361957076132LL; 
END
CASE(5)
	string request_[] = {
		"1.1.1.1",
		"3.3.3.3",
		"5.5.5.5",
		"7.7.7.7",
		"9.9.9.9",
		"11.11.11.11",
		"13.13.13.13",
		"15.15.15.15",
		"17.17.17.17",
		"19.19.19.19",
		"21.21.21.21",
		"23.23.23.23",
		"25.25.25.25",
		"27.27.27.27",
		"29.29.29.29",
		"31.31.31.31",
		"33.33.33.33",
		"35.35.35.35",
		"37.37.37.37",
		"39.39.39.39",
		"41.41.41.41",
		"43.43.43.43",
		"45.45.45.45",
		"47.47.47.47",
		"49.49.49.49",
		"51.51.51.51",
		"53.53.53.53",
		"55.55.55.55",
		"57.57.57.57",
		"59.59.59.59",
};
	  vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_)); 
	  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};
	  vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 
	long long _ = -1LL; 
END
/*
CASE(6)
	string request_[] = ;
	  vector <string> request(request_, request_+sizeof(request_)/sizeof(*request_)); 
	int price_[] = ;
	  vector <int> price(price_, price_+sizeof(price_)/sizeof(*price_)); 
	long long _ = LL; 
END
*/
}
// END CUT HERE