From 1e05f756960c0b0c7fbd5acc11e5c0ae29134dcc Mon Sep 17 00:00:00 2001
From: crupest <crupest@outlook.com>
Date: Sun, 25 Oct 2020 17:16:31 +0800
Subject: Add algorithm contest 2.

---
 algorithm-contest-2/solution/4.cpp | 48 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 48 insertions(+)
 create mode 100644 algorithm-contest-2/solution/4.cpp

(limited to 'algorithm-contest-2/solution/4.cpp')

diff --git a/algorithm-contest-2/solution/4.cpp b/algorithm-contest-2/solution/4.cpp
new file mode 100644
index 0000000..93c9190
--- /dev/null
+++ b/algorithm-contest-2/solution/4.cpp
@@ -0,0 +1,48 @@
+#define _CRT_SECURE_NO_WARNINGS
+#include <iostream>
+#include <cstdio>
+#include <cstring>
+#include <algorithm>
+#include <vector>
+#include <set>
+#include <map>
+#include <cmath>
+#include <unordered_map>
+#define x first
+#define y second
+#define pub push_back
+#define MP make_pair
+#define LL long long
+using namespace std;
+typedef pair<int, int> PII;
+
+const int MAXN = 1e5 + 5;
+int n, k, h[MAXN], w[MAXN];
+
+bool check(int m) {
+    if (m == 0) return true;
+    int cnt = 0;
+    for (int i = 0; i < n; i++) {
+        cnt += (h[i] / m) * (w[i] / m);
+    }
+    return cnt >= k;
+}
+
+int main(void) {
+    cin >> n >> k;
+    int mx = 0;
+    for (int i = 0; i < n; i++) {
+        scanf("%d", &h[i]);
+        scanf("%d", &w[i]);
+        mx = max(mx, max(h[i], w[i]));
+    }
+
+    int l = 0, r = mx;
+    while (l < r) {
+        int m = (l + r + 1) >> 1;
+        if (check(m)) l = m;
+        else r = m - 1;
+    }
+    cout << r;
+    return 0;
+}
\ No newline at end of file
-- 
cgit v1.2.3