1 files changed, 52 insertions, 0 deletions
diff --git a/store/works/life/algorithm-contest-3/code/5.cpp b/store/works/life/algorithm-contest-3/code/5.cpp
new file mode 100644
index 0000000..8d70a55
--- /dev/null
+++ b/store/works/life/algorithm-contest-3/code/5.cpp
@@ -0,0 +1,52 @@
+#include <algorithm>
+#include <iostream>
+
+int N, K;
+long long A[100010];
+
+long long M = 1000000009;
+
+int main() {
+  std::ios_base::sync_with_stdio(false);
+  std::cin.tie(nullptr);
+
+  std::cin >> N >> K;
+
+  for (int i = 0; i < N; i++) {
+    std::cin >> A[i];
+  }
+
+  std::sort(A, A + N);
+
+  long long result = 1;
+  int left = 0, right = N - 1;
+  long long sign = 1;
+  int k = K;
+
+  if (k % 2) {
+    result = A[N - 1];
+    right--;
+    k--;
+
+    if (result < 0) {
+      sign = -1;
+    }
+  }
+
+  while (k) {
+    long long x = A[left] * A[left + 1], y = A[right] * A[right - 1];
+
+    if (x * sign > y * sign) {
+      result = x % M * result % M;
+      left += 2;
+    } else {
+      result = y % M * result % M;
+      right -= 2;
+    }
+    k -= 2;
+  }
+
+  std::cout << result;
+
+  return 0;
+}