3fe379f029 2012-11-30 kinaba: #include <iostream> 3fe379f029 2012-11-30 kinaba: #include <sstream> 3fe379f029 2012-11-30 kinaba: #include <iomanip> 3fe379f029 2012-11-30 kinaba: #include <vector> 3fe379f029 2012-11-30 kinaba: #include <string> 3fe379f029 2012-11-30 kinaba: #include <map> 3fe379f029 2012-11-30 kinaba: #include <set> 3fe379f029 2012-11-30 kinaba: #include <algorithm> 3fe379f029 2012-11-30 kinaba: #include <numeric> 3fe379f029 2012-11-30 kinaba: #include <iterator> 3fe379f029 2012-11-30 kinaba: #include <functional> 3fe379f029 2012-11-30 kinaba: #include <complex> 3fe379f029 2012-11-30 kinaba: #include <queue> 3fe379f029 2012-11-30 kinaba: #include <stack> 3fe379f029 2012-11-30 kinaba: #include <cmath> 3fe379f029 2012-11-30 kinaba: #include <cassert> 3fe379f029 2012-11-30 kinaba: using namespace std; 3fe379f029 2012-11-30 kinaba: typedef long long LL; 3fe379f029 2012-11-30 kinaba: typedef long double LD; 3fe379f029 2012-11-30 kinaba: typedef complex<LD> CMP; 3fe379f029 2012-11-30 kinaba: 3fe379f029 2012-11-30 kinaba: class ICPCBalloons { public: 3fe379f029 2012-11-30 kinaba: static const int INF = 0x3fffffff; 3fe379f029 2012-11-30 kinaba: 3fe379f029 2012-11-30 kinaba: int minRepaintings(vector <int> balloonCount, string balloonSize, vector <int> maxAccepted) 3fe379f029 2012-11-30 kinaba: { 3fe379f029 2012-11-30 kinaba: const int N = balloonCount.size(); 3fe379f029 2012-11-30 kinaba: const int Q = maxAccepted.size(); 3fe379f029 2012-11-30 kinaba: 3fe379f029 2012-11-30 kinaba: vector<int> M, L; 3fe379f029 2012-11-30 kinaba: for(int i=0; i<N; ++i) 3fe379f029 2012-11-30 kinaba: (balloonSize[i]=='M' ? M : L).push_back(balloonCount[i]); 3fe379f029 2012-11-30 kinaba: 3fe379f029 2012-11-30 kinaba: sort(M.rbegin(), M.rend()); 3fe379f029 2012-11-30 kinaba: sort(L.rbegin(), L.rend()); 3fe379f029 2012-11-30 kinaba: sort(maxAccepted.rbegin(), maxAccepted.rend()); 3fe379f029 2012-11-30 kinaba: 3fe379f029 2012-11-30 kinaba: int best = INF; 3fe379f029 2012-11-30 kinaba: 3fe379f029 2012-11-30 kinaba: for(int m=0; m<(1<<Q); ++m) { 3fe379f029 2012-11-30 kinaba: vector<int> forM, forL; 3fe379f029 2012-11-30 kinaba: for(int i=0; i<Q; ++i) 3fe379f029 2012-11-30 kinaba: (m & (1<<i) ? forM : forL).push_back(maxAccepted[i]); 3fe379f029 2012-11-30 kinaba: best = min(best, cost(M, forM)+cost(L, forL)); 3fe379f029 2012-11-30 kinaba: } 3fe379f029 2012-11-30 kinaba: return best==INF ? -1 : best; 3fe379f029 2012-11-30 kinaba: } 3fe379f029 2012-11-30 kinaba: 3fe379f029 2012-11-30 kinaba: int cost(const vector<int>& b, const vector<int> q) 3fe379f029 2012-11-30 kinaba: { 3fe379f029 2012-11-30 kinaba: int more = 0; 3fe379f029 2012-11-30 kinaba: int less = 0; 3fe379f029 2012-11-30 kinaba: for(int i=0; i<q.size(); ++i) { 3fe379f029 2012-11-30 kinaba: int bi = i<b.size() ? b[i] : 0; 3fe379f029 2012-11-30 kinaba: if(bi >= q[i]) { 3fe379f029 2012-11-30 kinaba: more += bi - q[i]; 3fe379f029 2012-11-30 kinaba: } else { 3fe379f029 2012-11-30 kinaba: less += q[i] - bi; 3fe379f029 2012-11-30 kinaba: } 3fe379f029 2012-11-30 kinaba: } 3fe379f029 2012-11-30 kinaba: for(int i=q.size(); i<b.size(); ++i) 3fe379f029 2012-11-30 kinaba: more += b[i]; 3fe379f029 2012-11-30 kinaba: return (more>=less ? less : INF); 3fe379f029 2012-11-30 kinaba: } 3fe379f029 2012-11-30 kinaba: }; 3fe379f029 2012-11-30 kinaba: 3fe379f029 2012-11-30 kinaba: // BEGIN CUT HERE 3fe379f029 2012-11-30 kinaba: #include <ctime> 3fe379f029 2012-11-30 kinaba: double start_time; string timer() 3fe379f029 2012-11-30 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 3fe379f029 2012-11-30 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 3fe379f029 2012-11-30 kinaba: { os << "{ "; 3fe379f029 2012-11-30 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 3fe379f029 2012-11-30 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 3fe379f029 2012-11-30 kinaba: void verify_case(const int& Expected, const int& Received) { 3fe379f029 2012-11-30 kinaba: bool ok = (Expected == Received); 3fe379f029 2012-11-30 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 3fe379f029 2012-11-30 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 3fe379f029 2012-11-30 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 3fe379f029 2012-11-30 kinaba: #define END verify_case(_, ICPCBalloons().minRepaintings(balloonCount, balloonSize, maxAccepted));} 3fe379f029 2012-11-30 kinaba: int main(){ 3fe379f029 2012-11-30 kinaba: 3fe379f029 2012-11-30 kinaba: CASE(0) 3fe379f029 2012-11-30 kinaba: int balloonCount_[] = {100}; 3fe379f029 2012-11-30 kinaba: vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonCount_)/sizeof(*balloonCount_)); 3fe379f029 2012-11-30 kinaba: string balloonSize = "L"; 3fe379f029 2012-11-30 kinaba: int maxAccepted_[] = {1,2,3,4,5}; 3fe379f029 2012-11-30 kinaba: vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted_)/sizeof(*maxAccepted_)); 3fe379f029 2012-11-30 kinaba: int _ = 10; 3fe379f029 2012-11-30 kinaba: END 3fe379f029 2012-11-30 kinaba: CASE(1) 3fe379f029 2012-11-30 kinaba: int balloonCount_[] = {100}; 3fe379f029 2012-11-30 kinaba: vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonCount_)/sizeof(*balloonCount_)); 3fe379f029 2012-11-30 kinaba: string balloonSize = "M"; 3fe379f029 2012-11-30 kinaba: int maxAccepted_[] = {10,20,30,40,50}; 3fe379f029 2012-11-30 kinaba: vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted_)/sizeof(*maxAccepted_)); 3fe379f029 2012-11-30 kinaba: int _ = -1; 3fe379f029 2012-11-30 kinaba: END 3fe379f029 2012-11-30 kinaba: CASE(2) 3fe379f029 2012-11-30 kinaba: int balloonCount_[] = {5,6,1,5,6,1,5,6,1}; 3fe379f029 2012-11-30 kinaba: vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonCount_)/sizeof(*balloonCount_)); 3fe379f029 2012-11-30 kinaba: string balloonSize = "MLMMLMMLM"; 3fe379f029 2012-11-30 kinaba: int maxAccepted_[] = {7,7,4,4,7,7}; 3fe379f029 2012-11-30 kinaba: vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted_)/sizeof(*maxAccepted_)); 3fe379f029 2012-11-30 kinaba: int _ = 6; 3fe379f029 2012-11-30 kinaba: END 3fe379f029 2012-11-30 kinaba: CASE(3) 3fe379f029 2012-11-30 kinaba: int balloonCount_[] = {100,100}; 3fe379f029 2012-11-30 kinaba: vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonCount_)/sizeof(*balloonCount_)); 3fe379f029 2012-11-30 kinaba: string balloonSize = "ML"; 3fe379f029 2012-11-30 kinaba: int maxAccepted_[] = {50,51,51}; 3fe379f029 2012-11-30 kinaba: vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted_)/sizeof(*maxAccepted_)); 3fe379f029 2012-11-30 kinaba: int _ = -1; 3fe379f029 2012-11-30 kinaba: END 3fe379f029 2012-11-30 kinaba: CASE(4) 3fe379f029 2012-11-30 kinaba: int balloonCount_[] = {8,5,1,4,1,1,3,1,3,3,5,4,5,6,9}; 3fe379f029 2012-11-30 kinaba: vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonCount_)/sizeof(*balloonCount_)); 3fe379f029 2012-11-30 kinaba: string balloonSize = "MMMLLLMMLLMLMLM"; 3fe379f029 2012-11-30 kinaba: int maxAccepted_[] = {3,5,3,3,5,6,4,6,4,2,3,7,1,5,2}; 3fe379f029 2012-11-30 kinaba: vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted_)/sizeof(*maxAccepted_)); 3fe379f029 2012-11-30 kinaba: int _ = 5; 3fe379f029 2012-11-30 kinaba: END 3fe379f029 2012-11-30 kinaba: CASE(5) 3fe379f029 2012-11-30 kinaba: int balloonCount_[] = {1,18,4,7,19,7,7,1,4,8,10,5,14,13,8,22,6,3,13,5,3,4,2,1,3,15,19,4,5,9,4,11,2,7,12,20,11,26,22,7,2,10,9,20,13,20,2,9,11,9}; 3fe379f029 2012-11-30 kinaba: vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonCount_)/sizeof(*balloonCount_)); 3fe379f029 2012-11-30 kinaba: string balloonSize = "LLMLLLLMLLLLLLLLLLLLMLLLLLLLLLLMMLMLLLMLLLLLLLLMLL"; 3fe379f029 2012-11-30 kinaba: int maxAccepted_[] = {44,59,29,53,16,23,13,14,29,42,13,15,66,4,47}; 3fe379f029 2012-11-30 kinaba: vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted_)/sizeof(*maxAccepted_)); 3fe379f029 2012-11-30 kinaba: int _ = 210; 3fe379f029 2012-11-30 kinaba: END 3fe379f029 2012-11-30 kinaba: /* 3fe379f029 2012-11-30 kinaba: CASE(6) 3fe379f029 2012-11-30 kinaba: int balloonCount_[] = ; 3fe379f029 2012-11-30 kinaba: vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonCount_)/sizeof(*balloonCount_)); 3fe379f029 2012-11-30 kinaba: string balloonSize = ; 3fe379f029 2012-11-30 kinaba: int maxAccepted_[] = ; 3fe379f029 2012-11-30 kinaba: vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted_)/sizeof(*maxAccepted_)); 3fe379f029 2012-11-30 kinaba: int _ = ; 3fe379f029 2012-11-30 kinaba: END 3fe379f029 2012-11-30 kinaba: CASE(7) 3fe379f029 2012-11-30 kinaba: int balloonCount_[] = ; 3fe379f029 2012-11-30 kinaba: vector <int> balloonCount(balloonCount_, balloonCount_+sizeof(balloonCount_)/sizeof(*balloonCount_)); 3fe379f029 2012-11-30 kinaba: string balloonSize = ; 3fe379f029 2012-11-30 kinaba: int maxAccepted_[] = ; 3fe379f029 2012-11-30 kinaba: vector <int> maxAccepted(maxAccepted_, maxAccepted_+sizeof(maxAccepted_)/sizeof(*maxAccepted_)); 3fe379f029 2012-11-30 kinaba: int _ = ; 3fe379f029 2012-11-30 kinaba: END 3fe379f029 2012-11-30 kinaba: */ 3fe379f029 2012-11-30 kinaba: } 3fe379f029 2012-11-30 kinaba: // END CUT HERE