Artifact Content
Not logged in

Artifact aab4c30d49ab7bd6d78e8de4c610b46ef0e20d47


#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;

struct Event
{
	int i, T, C, P;
	double P_total;
	bool has_next;
	Event(int i, int T, int C, int P) : i(i), T(T), C(C), P(P) {}
	bool operator<(const Event& rhs) const { return T < rhs.T; }
};

class NewItemShop { public:
	double getMaximum(int swords, vector <string> customers)
	{
		vector<Event> ev;
		for(size_t i=0; i<customers.size(); ++i)
		{
			for(size_t k=0; k<customers[i].size(); ++k)
				if( customers[i][k] == ',' )
					customers[i][k] = ' ';
			stringstream ss(customers[i]);
			for(int T,C,P; ss>>T>>C>>P; )
				ev.push_back(Event((int)i,T,C,P));
		}
		sort(ev.begin(), ev.end());
		for(int i=0; i<ev.size(); ++i)
		{
			ev[i].P_total = 100;
			ev[i].has_next = false;
			for(int k=i+1; k<ev.size(); ++k)
				if( ev[k].i == ev[i].i )
					ev[i].has_next = true;
			for(int k=i-1; k>=0; --k)
				if( ev[k].i == ev[i].i )
					ev[i].P_total -= ev[k].P;
		}
		return rec(0, ev, swords, 0);
	}

	map<int, double> memo;
	double rec(int i, const vector<Event>& ev, int swords, int mask)
	{
		if( i==ev.size() || swords==0 )
			return 0;
		int key = (mask*ev.size() + i) * 25 + swords;
		if( memo.count(key) )
			return memo[key];

		const int ID = ev[i].i;
		const double C = ev[i].C;
		const double P = ev[i].P / ev[i].P_total;
		const int newmask = (ev[i].has_next ? mask|(1<<ID) : mask);

		if( (1<<ID) & mask )
			return memo[key] = rec(i+1, ev, swords, mask);
		return memo[key] =
			      P * max(C+rec(i+1, ev, swords-1, newmask), rec(i+1, ev, swords, newmask))
			+ (1-P) * rec(i+1, ev, swords, mask);
	}
};

// 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 double& Expected, const double& Received) {
 bool ok = (abs(Expected - Received) < 1e-9);
 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(_, NewItemShop().getMaximum(swords, customers));}
int main(){

CASE(0)
	int swords = 1; 
	string customers_[] = { "8,1,80 16,100,11", "12,10,100" };
	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_)); 
	double _ = 19.0; 
END
CASE(1)
	int swords = 2; 
	string customers_[] = { "8,1,80 16,100,11", "12,10,100" };
	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_)); 
	double _ = 21.8; 
END
CASE(2)
	int swords = 1; 
	string customers_[] = { "0,90,25 2,90,25 4,90,25 6,90,25", "7,100,80" };
	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_)); 
	double _ = 90.0; 
END
CASE(3)
	int swords = 3; 
	string customers_[] = { "17,31,41 20,59,26 23,53,5", "19,89,79", "16,32,38 22,46,26", "18,43,38 21,32,7" };
	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_)); 
	double _ = 135.5121414; 
END
CASE(4)
	int swords = 5; 
	string customers_[] = { "1,1,10", "2,2,9", "3,3,8", "4,4,7", "5,5,6", "6,6,5", "7,7,4", "8,8,3", "9,9,2", "10,10,1" };
	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_)); 
	double _ = 2.1999744634845344; 
END
/*
CASE(5)
	int swords = ; 
	string customers_[] = ;
	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_)); 
	double _ = ; 
END
CASE(6)
	int swords = ; 
	string customers_[] = ;
	  vector <string> customers(customers_, customers_+sizeof(customers_)/sizeof(*customers_)); 
	double _ = ; 
END
*/
}
// END CUT HERE