fork download
copy 
  1. /*
  2. *from V3 with some modification to handle large output
  3. *reducing input size
  4. *sorting with comparator that relies on income of jobs, the order of jobs can matter
  5. 	note: try to modify comparator but the result is still the same
  6. *N <= 200
  7. *luu lai level ma tai do dat duoc maxIncome[bitmask], chi goi dfs khi ma no co the dat dc maxIncome som hon (level nho hon) ~ chia 2 truong hop ro rang:
  8.  curIncome > or == maxIncome[bitmask]
  9. */
  10. #include <string>
  11. #include <vector>
  12. #include <map>
  13. #include <algorithm>
  14. #include <iostream>
  15. using namespace std;
  16.  
  17. struct job {
  18. 	vector<string> names;
  19. 	int income;
  20. 	int time;
  21. };
  22. map<string, int> dayToNum;
  23. string day[7] = { "mon","tue","wed","thu","fri","sat","sun" };
  24. map<char, int> timeToNum;
  25. char times[3] = { 'M','A','E' };
  26. int avai = (1 << 21) - 1, maxx = 0, curIncome = 0, szList = 0;
  27. vector<job> jobs;
  28. int list[21];
  29. int maxIncome[(1 << 21)], jobs0[(1 << 21)];
  30. bool taken[(1 << 21)];
  31. int uniqueBitmasks[220];
  32. vector<string> names[(1 << 21)];
  33. int cnt = 0, szUniqueBitmasks = 0;
  34. int xxxx=0;
  35.  
  36. void printWorkTime(int x) {
  37. 	for (int i = 0; i < 21; i++) {
  38. 		int b = x % 2;
  39. 		x /= 2;
  40. 		if (b) {
  41. 			int id, id2;
  42. 			id = 6 - i / 3;
  43. 			id2 = 2 - i % 3;
  44. 			cout << "          ";
  45. 			cout << day[id] << " " << times[id2] << '\n';
  46. 		}
  47. 	}
  48. }
  49. void dfs(int x) {
  50. 	//choose the job
  51. 	if ((avai&jobs[x].time) == 0) {
  52. 		avai ^= jobs[x].time;
  53. 		curIncome += jobs[x].income;
  54. 		int chk=(curIncome > maxIncome[avai]);
  55. 		maxIncome[avai] = max(maxIncome[avai], curIncome);
  56. 		if (x == jobs.size() - 1)
  57. 			maxx = max(maxx, curIncome);
  58. 		else
  59. 			if (chk)
  60. 				dfs(x + 1);
  61. 		curIncome -= jobs[x].income;
  62. 		avai ^= jobs[x].time;
  63. 	}
  64. 	//dont choose the job
  65. 	int chk=(curIncome > maxIncome[avai]);
  66. 	maxIncome[avai] = max(maxIncome[avai], curIncome);
  67. 	if (x == jobs.size() - 1)
  68. 		maxx = max(maxx, curIncome);
  69. 	else
  70. 		if (chk || (curIncome==0 && curIncome == maxIncome[avai]))
  71. 			dfs(x + 1);
  72. }
  73. void printCombinationJobs() {
  74. 	cnt++;
  75. 	//cout << "Combo " << cnt << ":\n";
  76. 	int tmp=1;
  77. 	for (int i = 0; i < szList; i++) {
  78. 		//cout << "     ";
  79. 		//for (int j = 0; j < jobs[list[i]].names.size(); j++)
  80. 			//cout << jobs[list[i]].names[j] << ' ';
  81. 		tmp*=jobs[list[i]].names.size();
  82. 		//cout<<i<<": "<<jobs[list[i]].names.size()<<'\n';
  83. 		//cout << "\n";
  84. 		//printWorkTime(jobs[list[i]].time);
  85. 	}
  86. 	xxxx+=tmp;
  87. 	//cout<<"=========="<<tmp<<' '<<xxxx<<"\n";
  88.  
  89. }
  90. void findAll(int x) {
  91. 	//choose the job
  92. 	if ((avai&jobs[x].time) == 0) {
  93. 		avai ^= jobs[x].time;
  94. 		curIncome += jobs[x].income;
  95. 		list[szList] = x;
  96. 		szList++;
  97. 		if (x == jobs.size() - 1) {
  98. 			if (curIncome == maxx)
  99. 				printCombinationJobs();
  100. 		}
  101. 		else
  102. 			if (curIncome == maxIncome[avai])
  103. 				findAll(x + 1);
  104. 		szList--;
  105. 		curIncome -= jobs[x].income;
  106. 		avai ^= jobs[x].time;
  107. 	}
  108. 	//dont choose the job
  109. 	if (x == jobs.size() - 1) {
  110. 		if (curIncome == maxx)
  111. 			printCombinationJobs();
  112. 	}
  113. 	else
  114. 		if (curIncome == maxIncome[avai])
  115. 			findAll(x + 1);
  116. }
  117. bool opt(job &a, job &b) {
  118. 	return (a.income > b.income);
  119. }
  120.  
  121. int main()
  122. {
  123. 	ios::sync_with_stdio(0);
  124. 	cin.tie(0); cout.tie(0);
  125. 	for (int i = 0; i < 7; i++)
  126. 		dayToNum.insert(make_pair(day[i], i));
  127. 	for (int i = 0; i < 3; i++)
  128. 		timeToNum.insert(make_pair(times[i], i));
  129. 	//read available time
  130. 	int n;
  131. 	cin >> n;
  132. 	for (int i = 0; i < n; i++) {
  133. 		string st;
  134. 		cin >> st;
  135. 		int id = dayToNum[st];
  136. 		cin >> st;
  137. 		for (int i = 0; i < st.size(); i++) {
  138. 			int id2 = timeToNum[st[i]];
  139. 			int tmp = (1 << (20 - id * 3 - id2));
  140. 			avai ^= tmp;
  141. 		}
  142. 	}
  143. 	//read jobs
  144. 	cin >> n;
  145. 	for (int i = 0; i < n; i++) {
  146. 		string name, typ;
  147. 		cin >> name >> typ;
  148. 		int income, m;
  149. 		cin >> income >> m;
  150. 		int time = 0, shifts = 0;
  151. 		//read date and time
  152. 		for (int j = 0; j < m; j++) {
  153. 			string d, st;
  154. 			cin >> d >> st;
  155. 			int id = dayToNum[d], id2, tmp;
  156. 			for (int k = 0; k < st.size(); k++) {
  157. 				char ch = st[k];
  158. 				id2 = timeToNum[ch];
  159. 				tmp = (1 << (20 - id * 3 - id2));
  160. 				if (typ == "flexible") {
  161. 					//flex job
  162. 					if (income > jobs0[tmp]) {
  163. 						if (!taken[tmp])
  164. 							taken[tmp] = 1,
  165. 							uniqueBitmasks[szUniqueBitmasks] = tmp,
  166. 							szUniqueBitmasks++;
  167. 						jobs0[tmp] = income;
  168. 						names[tmp].clear();
  169. 						names[tmp].push_back(name);
  170. 					}
  171. 					else if (income == jobs0[tmp]) 
  172. 						names[tmp].push_back(name);
  173. 				}
  174. 				else {
  175. 					shifts++;
  176. 					time ^= tmp;
  177. 				}
  178. 			}
  179. 		}
  180. 		//fixed job
  181. 		if (typ == "fixed")
  182. 			if (income*shifts > jobs0[time]) {
  183. 				if (!taken[time])
  184. 					taken[time] = 1,
  185. 					uniqueBitmasks[szUniqueBitmasks] = time,
  186. 					szUniqueBitmasks++;
  187. 				jobs0[time] = income*shifts;
  188. 				names[time].clear();
  189. 				names[time].push_back(name);
  190. 			}
  191. 			else if (income*shifts == jobs0[time])
  192. 				names[time].push_back(name);
  193. 	}
  194. 	//add all jobs from jobs0 to jobs
  195. 	jobs.resize(szUniqueBitmasks);
  196. 	for (int i = 0; i < szUniqueBitmasks; i++) {
  197. 		int bitmask = uniqueBitmasks[i];
  198. 		jobs[i].income = jobs0[bitmask];
  199. 		jobs[i].names = names[bitmask];
  200. 		jobs[i].time = bitmask;
  201. 	}
  202. 	//sort jobs, for faster runtime
  203. 	sort(jobs.begin(), jobs.end(), opt);
  204. 	//find max income
  205. 	dfs(0);
  206. 	cout << "Max income = " << maxx << '\n';
  207. 	//find all combinations which can give max income
  208. 	findAll(0);
  209. 	cout<<'\n'<<xxxx;
  210.  
  211. 	return 0;
  212. }
Success #stdin #stdout 0.02s 52700KB
comments (?)
stdin
copy 
7
mon MAE
tue MAE
wed MAE
thu MAE
fri MAE
sat MAE
sun MAE
2
1
fixed
200
1
mon MAE
2
fixed
200
1
tue MAE
stdout
copy 
Max income = 1200

1
https://ideone.com/BuRrgL
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!