From 99e2e923d0c77b02f3fb4ff648ea916954868606 Mon Sep 17 00:00:00 2001
From: Yuqian Yang <crupest@crupest.life>
Date: Fri, 28 Feb 2025 23:13:39 +0800
Subject: chore(store): move everything to store.

---
 store/works/life/algorithm-contest-3/code/5.cpp | 52 +++++++++++++++++++++++++
 1 file changed, 52 insertions(+)
 create mode 100644 store/works/life/algorithm-contest-3/code/5.cpp

(limited to 'store/works/life/algorithm-contest-3/code/5.cpp')

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;
+}
-- 
cgit v1.2.3