2024b9fa5d 2016-01-23 kinaba: #include <iostream> 2024b9fa5d 2016-01-23 kinaba: #include <sstream> 2024b9fa5d 2016-01-23 kinaba: #include <iomanip> 2024b9fa5d 2016-01-23 kinaba: #include <vector> 2024b9fa5d 2016-01-23 kinaba: #include <string> 2024b9fa5d 2016-01-23 kinaba: #include <map> 2024b9fa5d 2016-01-23 kinaba: #include <set> 2024b9fa5d 2016-01-23 kinaba: #include <algorithm> 2024b9fa5d 2016-01-23 kinaba: #include <numeric> 2024b9fa5d 2016-01-23 kinaba: #include <iterator> 2024b9fa5d 2016-01-23 kinaba: #include <functional> 2024b9fa5d 2016-01-23 kinaba: #include <complex> 2024b9fa5d 2016-01-23 kinaba: #include <queue> 2024b9fa5d 2016-01-23 kinaba: #include <stack> 2024b9fa5d 2016-01-23 kinaba: #include <cmath> 2024b9fa5d 2016-01-23 kinaba: #include <cassert> 2024b9fa5d 2016-01-23 kinaba: #include <tuple> 2024b9fa5d 2016-01-23 kinaba: using namespace std; 2024b9fa5d 2016-01-23 kinaba: typedef long long LL; 2024b9fa5d 2016-01-23 kinaba: typedef complex<double> CMP; 2024b9fa5d 2016-01-23 kinaba: 2024b9fa5d 2016-01-23 kinaba: class FiringEmployees { public: 2024b9fa5d 2016-01-23 kinaba: int fire(vector <int> manager, vector <int> salary, vector <int> productivity) 2024b9fa5d 2016-01-23 kinaba: { 2024b9fa5d 2016-01-23 kinaba: const int N = manager.size()+1; 2024b9fa5d 2016-01-23 kinaba: 2024b9fa5d 2016-01-23 kinaba: vector<vector<int>> children(N); 2024b9fa5d 2016-01-23 kinaba: for(int i=1; i<N; ++i) 2024b9fa5d 2016-01-23 kinaba: children[manager[i-1]].push_back(i); 2024b9fa5d 2016-01-23 kinaba: 2024b9fa5d 2016-01-23 kinaba: vector<int> best(N); 2024b9fa5d 2016-01-23 kinaba: for(int i=N-1; i>=0; --i) { 2024b9fa5d 2016-01-23 kinaba: int total = (i ? productivity[i-1] - salary[i-1] : 0); 2024b9fa5d 2016-01-23 kinaba: for(int u: children[i]) 2024b9fa5d 2016-01-23 kinaba: total += best[u]; 2024b9fa5d 2016-01-23 kinaba: if(total > 0) 2024b9fa5d 2016-01-23 kinaba: best[i] = total; 2024b9fa5d 2016-01-23 kinaba: } 2024b9fa5d 2016-01-23 kinaba: return best[0]; 2024b9fa5d 2016-01-23 kinaba: } 2024b9fa5d 2016-01-23 kinaba: }; 2024b9fa5d 2016-01-23 kinaba: 2024b9fa5d 2016-01-23 kinaba: // BEGIN CUT HERE 2024b9fa5d 2016-01-23 kinaba: #include <ctime> 2024b9fa5d 2016-01-23 kinaba: double start_time; string timer() 2024b9fa5d 2016-01-23 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 2024b9fa5d 2016-01-23 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 2024b9fa5d 2016-01-23 kinaba: { os << "{ "; 2024b9fa5d 2016-01-23 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 2024b9fa5d 2016-01-23 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 2024b9fa5d 2016-01-23 kinaba: void verify_case(const int& Expected, const int& Received) { 2024b9fa5d 2016-01-23 kinaba: bool ok = (Expected == Received); 2024b9fa5d 2016-01-23 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 2024b9fa5d 2016-01-23 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 2024b9fa5d 2016-01-23 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 2024b9fa5d 2016-01-23 kinaba: #define END verify_case(_, FiringEmployees().fire(manager, salary, productivity));} 2024b9fa5d 2016-01-23 kinaba: int main(){ 2024b9fa5d 2016-01-23 kinaba: 2024b9fa5d 2016-01-23 kinaba: CASE(0) 2024b9fa5d 2016-01-23 kinaba: int manager_[] = {0,0,0}; 2024b9fa5d 2016-01-23 kinaba: vector <int> manager(manager_, manager_+sizeof(manager_)/sizeof(*manager_)); 2024b9fa5d 2016-01-23 kinaba: int salary_[] = {1,2,3}; 2024b9fa5d 2016-01-23 kinaba: vector <int> salary(salary_, salary_+sizeof(salary_)/sizeof(*salary_)); 2024b9fa5d 2016-01-23 kinaba: int productivity_[] = {3,2,1}; 2024b9fa5d 2016-01-23 kinaba: vector <int> productivity(productivity_, productivity_+sizeof(productivity_)/sizeof(*productivity_)); 2024b9fa5d 2016-01-23 kinaba: int _ = 2; 2024b9fa5d 2016-01-23 kinaba: END 2024b9fa5d 2016-01-23 kinaba: CASE(1) 2024b9fa5d 2016-01-23 kinaba: int manager_[] = {0,1,2,3}; 2024b9fa5d 2016-01-23 kinaba: vector <int> manager(manager_, manager_+sizeof(manager_)/sizeof(*manager_)); 2024b9fa5d 2016-01-23 kinaba: int salary_[] = {4,3,2,1}; 2024b9fa5d 2016-01-23 kinaba: vector <int> salary(salary_, salary_+sizeof(salary_)/sizeof(*salary_)); 2024b9fa5d 2016-01-23 kinaba: int productivity_[] = {2,3,4,5}; 2024b9fa5d 2016-01-23 kinaba: vector <int> productivity(productivity_, productivity_+sizeof(productivity_)/sizeof(*productivity_)); 2024b9fa5d 2016-01-23 kinaba: int _ = 4; 2024b9fa5d 2016-01-23 kinaba: END 2024b9fa5d 2016-01-23 kinaba: CASE(2) 2024b9fa5d 2016-01-23 kinaba: int manager_[] = {0,1}; 2024b9fa5d 2016-01-23 kinaba: vector <int> manager(manager_, manager_+sizeof(manager_)/sizeof(*manager_)); 2024b9fa5d 2016-01-23 kinaba: int salary_[] = {1,10}; 2024b9fa5d 2016-01-23 kinaba: vector <int> salary(salary_, salary_+sizeof(salary_)/sizeof(*salary_)); 2024b9fa5d 2016-01-23 kinaba: int productivity_[] = {5,5}; 2024b9fa5d 2016-01-23 kinaba: vector <int> productivity(productivity_, productivity_+sizeof(productivity_)/sizeof(*productivity_)); 2024b9fa5d 2016-01-23 kinaba: int _ = 4; 2024b9fa5d 2016-01-23 kinaba: END 2024b9fa5d 2016-01-23 kinaba: CASE(3) 2024b9fa5d 2016-01-23 kinaba: int manager_[] = {0,1,2,1,2,3,4,2,3}; 2024b9fa5d 2016-01-23 kinaba: vector <int> manager(manager_, manager_+sizeof(manager_)/sizeof(*manager_)); 2024b9fa5d 2016-01-23 kinaba: int salary_[] = {5,3,6,8,4,2,4,6,7}; 2024b9fa5d 2016-01-23 kinaba: vector <int> salary(salary_, salary_+sizeof(salary_)/sizeof(*salary_)); 2024b9fa5d 2016-01-23 kinaba: int productivity_[] = {2,5,7,8,5,3,5,7,9}; 2024b9fa5d 2016-01-23 kinaba: vector <int> productivity(productivity_, productivity_+sizeof(productivity_)/sizeof(*productivity_)); 2024b9fa5d 2016-01-23 kinaba: int _ = 6; 2024b9fa5d 2016-01-23 kinaba: END 2024b9fa5d 2016-01-23 kinaba: CASE(4) 2024b9fa5d 2016-01-23 kinaba: int manager_[] = {0,0,1,1,2,2}; 2024b9fa5d 2016-01-23 kinaba: vector <int> manager(manager_, manager_+sizeof(manager_)/sizeof(*manager_)); 2024b9fa5d 2016-01-23 kinaba: int salary_[] = {1,1,1,2,2,2}; 2024b9fa5d 2016-01-23 kinaba: vector <int> salary(salary_, salary_+sizeof(salary_)/sizeof(*salary_)); 2024b9fa5d 2016-01-23 kinaba: int productivity_[] = {2,2,2,1,1,1}; 2024b9fa5d 2016-01-23 kinaba: vector <int> productivity(productivity_, productivity_+sizeof(productivity_)/sizeof(*productivity_)); 2024b9fa5d 2016-01-23 kinaba: int _ = 3; 2024b9fa5d 2016-01-23 kinaba: END 2024b9fa5d 2016-01-23 kinaba: /* 2024b9fa5d 2016-01-23 kinaba: CASE(5) 2024b9fa5d 2016-01-23 kinaba: int manager_[] = ; 2024b9fa5d 2016-01-23 kinaba: vector <int> manager(manager_, manager_+sizeof(manager_)/sizeof(*manager_)); 2024b9fa5d 2016-01-23 kinaba: int salary_[] = ; 2024b9fa5d 2016-01-23 kinaba: vector <int> salary(salary_, salary_+sizeof(salary_)/sizeof(*salary_)); 2024b9fa5d 2016-01-23 kinaba: int productivity_[] = ; 2024b9fa5d 2016-01-23 kinaba: vector <int> productivity(productivity_, productivity_+sizeof(productivity_)/sizeof(*productivity_)); 2024b9fa5d 2016-01-23 kinaba: int _ = ; 2024b9fa5d 2016-01-23 kinaba: END 2024b9fa5d 2016-01-23 kinaba: CASE(6) 2024b9fa5d 2016-01-23 kinaba: int manager_[] = ; 2024b9fa5d 2016-01-23 kinaba: vector <int> manager(manager_, manager_+sizeof(manager_)/sizeof(*manager_)); 2024b9fa5d 2016-01-23 kinaba: int salary_[] = ; 2024b9fa5d 2016-01-23 kinaba: vector <int> salary(salary_, salary_+sizeof(salary_)/sizeof(*salary_)); 2024b9fa5d 2016-01-23 kinaba: int productivity_[] = ; 2024b9fa5d 2016-01-23 kinaba: vector <int> productivity(productivity_, productivity_+sizeof(productivity_)/sizeof(*productivity_)); 2024b9fa5d 2016-01-23 kinaba: int _ = ; 2024b9fa5d 2016-01-23 kinaba: END 2024b9fa5d 2016-01-23 kinaba: */ 2024b9fa5d 2016-01-23 kinaba: } 2024b9fa5d 2016-01-23 kinaba: // END CUT HERE