fork download
copy 
  1. #include <cstdio>
  2. #include <climits>
  3. #include <queue>
  4. #include <map>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. auto process(auto&& inp)
  9. {
  10. 	using State = tuple<int, int, vector<int>>;
  11. 	//          get<?>:  0,    1,       2
  12. 	// 상태 표현: 위치, 마지막으로 이용한 점프, 남은 점프 개수
  13.  
  14. 	map<State, int> min_cost;
  15. 	// 다이나믹 프로그래밍(DP) 테이블,
  16. 	// sparse하니까(중간중간 빈 칸이 많으니까) 배열 대신 std::map 이용.
  17.  
  18. 	vector<int>&& moves = move(inp.first);
  19. 	vector<int>&& costs = move(inp.second);
  20. 	int n = costs.size(), m = moves.size();
  21.  
  22. 	// 우선순위 큐 (비용이 최소인 pair<비용, 상태>를 얻기 위해 씀).
  23. 	priority_queue<pair<int, State>,
  24. 					//first,  second
  25. 				   vector<pair<int, State>>,
  26. 				   greater<pair<int, State>>> que;
  27. 				   // 최소 힙(아래 url에서 찾을 수 있다).
  28. 				   // kks227.blog.me/220791188929
  29.  
  30. 	// 시작 상태 (비용: 0, 상태: 0번째 칸(다리 밖), 마지막으로 이용한 점프: 없음(-1), 이용 가능한 점프들 수)
  31. 	que.push(make_pair(0, make_tuple(0, -1, moves)));
  32.  
  33. 	// 다익스트라 최단경로 알고리즘
  34. 	// kks227.blog.me/220796029558
  35. 	while (!que.empty()) {
  36. 		auto current = que.top();
  37. 		que.pop();
  38. 		// 현재 큐에서 가장 작은 비용을 갖는 상태를 꺼냄
  39. 		if (current.first > min_cost[current.second]) continue;
  40. 		// 이미 끝난 상태(위의 블로그 글 보면 설명 있음)면 넘어가자
  41. 		if (get<0>(current.second) + 1 == n) { // 답(마지막 칸을 밟음)을 찾음
  42. 			return current.first;
  43. 		}
  44. 		for (int i = 0; i < m; i++) if (get<1>(current.second) != i) {
  45. 						// 마지막으로 이용한 점프가 i가 아니면
  46. 			auto next = current; // 지금 상태를 복사해서 다음 상태를 만든다
  47. 			if ((get<0>(next.second) += i + 1) >= n) continue;
  48. 			// 점프해서 다리 밖으로 나가버리는 경우는 안되고
  49. 			if (--get<2>(next.second)[i] < 0) continue;
  50. 			// 점프 개수 초과해서 사용할 수 없다(남은 개수가 0인 점프를 이용하면 안된다).
  51. 			// 동시에 점프 개수 깎음(-- 연산자).
  52. 			get<1>(next.second) = i;
  53. 			// 다음 상태에서 마지막으로 이용한 점프는 i
  54. 			next.first += costs[get<0>(next.second)];
  55. 			// 점프한 칸의 비용을 더해주고
  56. 			if (!min_cost.count(next.second) ||
  57. 				min_cost[next.second] > next.first) {
  58. 				// 다음 상태가 여지껏 방문한 적 없는 상태거나 / 이렇게 가는 비용이 더 저렴하면
  59. 				min_cost[next.second] = next.first;
  60. 				que.push(next);
  61. 				// 비용을 갱신하고 큐에 또 넣는다.
  62. 				// 여기서 다른 상태로 또 뻗어나가면 다른 상태도 비용을 깎을 수 있을지 모르니까.
  63. 			}
  64. 		}
  65. 	}
  66.  
  67. 	return -1;
  68. }
  69.  
  70. auto input()
  71. {
  72. 	int n, m;
  73. 	scanf("%d%d", &n, &m); // n: length, m: moves
  74. 	vector<int> counts(m);
  75. 	vector<int> costs(++n);
  76. 	for (int i = 0; i < m; i++) scanf("%d", &counts[i]);
  77. 	for (int i = 1; i < n; i++) scanf("%d", &costs[i]);
  78. 	return make_pair(counts, costs);
  79. }
  80.  
  81. void output(auto&& ans)
  82. {
  83. 	if (ans == -1) puts("My mother is dead.");
  84. 	else printf("My mother is fucked by %d different dicks.\n", ans);
  85. }
  86.  
  87. int main() {
  88. 	output(process(input()));
  89. 	return 0;
  90. }
Success #stdin #stdout 1.14s 100032KB
comments (?)
stdin
copy 
100 10
97 18 10 25 4 1 8 7 3 2
89 71 73 98 79 24 21 39 54 44 28 18 18 46 30 99 37 78 26 11 64 90 39 92 10 92 27 72 34 75 8 80 48 29 88 55 32 69 73 100 57 100 82 99 46 61 19 73 59 33 47 8 15 5 63 50 44 27 11 53 36 43 74 71 52 53 8 54 51 3 20 76 92 80 84 52 49 89 49 57 19 99 59 38 87 1 67 29 79 33 69 66 27 22 80 4 13 54 24 39
stdout
copy 
My mother is fucked by 255 different dicks.
https://ideone.com/avIMAq
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!