#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