Solved a bunch of problems

1 files changed, 33 insertions, 23 deletions

diff --git a/contests/Starters78/D/main.cpp b/contests/Starters78/D/main.cpp
index 3865920..07ec32f 100755
--- a/contests/Starters78/D/main.cpp
+++ b/contests/Starters78/D/main.cpp
@@ -73,35 +73,45 @@ void print(T val, TS... vals) {
  */
 
 void solve() {
-  int n, t;
-  cin >> n >> t;
-  vll p(n), b(n);
-  int ans = 0;
-  for (auto &x : p) cin >> x;
-  for (auto &x : b) cin >> x;
-  vector<pair<ll, int>> tot(n); 
+  int n, k;
+  cin >> n >> k;
+  vector<pair<int, int>> p(n);
   for (int i = 0; i < n; i++) {
-    tot[i].first = p[i] + b[i];
-    tot[i].second = i;
+    cin >> p[i].second;
   }
-  sort(all(tot));
-  vector<bool> vis(n);
   for (int i = 0; i < n; i++) {
-    if (t - tot[i].first >= 0) {
-      vis[tot[i].second] = true;
-      ans++;
-      t -= tot[i].first;
-    } 
+    cin >> p[i].first;
+    p[i].first += p[i].second;
   }
-  for (int i = 0; i < n; i++) {
-    if (t - p[i] >= 0 && !vis[i]) {
-      vis[i] = true;
-      ans++;
-      break;
+  sort(p.begin(), p.end());
+  vector<long long> sum(n + 1);
+  vector<int> mx(n + 1);
+  mx[0] = p[0].second;
+  for (int i = 1; i <= n; i++) {
+    sum[i] = p[i - 1].first + sum[i - 1];
+    mx[i] = max(mx[i - 1], p[i].first - p[i].second);
+  }
+  printv(sum);
+  printv(mx);
+  int lo = 0, hi = n + 1;
+  while (hi - lo > 1) {
+    int mid = (lo + hi) >> 1;
+    bool ok = ((sum[mid] - mx[mid - 1]) <= k) && (mid > 1);
+    if (!ok) {
+      for (int i = mid; i < n; i++) {
+        if (sum[mid - 1] + p[i].second <= k) {
+          ok = true;
+          break;
+        }
+      }
+    }
+    if (ok) {
+      lo = mid;
+    } else {
+      hi = mid;
     }
   }
-  cout << ans << '\n';
-
+  cout << lo << '\n';
 }
 
 int main () {