fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const ll INF = 4e18;
  5.  
  6. int main() {
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.  
  10.     int N, K;
  11.     cin >> N >> K;
  12.     vector<int> v(N);
  13.     vector<ll> c(N);
  14.     ll maxC = 0;
  15.     for (int i = 0; i < N; i++) {
  16.         cin >> v[i] >> c[i];
  17.         maxC = max(maxC, c[i]);
  18.     }
  19.  
  20.     auto can = [&](ll M) -> bool {
  21.         // dp[val] = 최소 (c_i - M) 합
  22.         static ll dp[5001];
  23.         for (int i = 0; i <= 5000; i++) dp[i] = INF;
  24.         dp[0] = 0;
  25.  
  26.         for (int i = 0; i < N; i++) {
  27.             ll w = c[i] - M;
  28.             for (int val = 5000; val >= v[i]; val--) {
  29.                 if (dp[val - v[i]] != INF)
  30.                     dp[val] = min(dp[val], dp[val - v[i]] + w);
  31.             }
  32.         }
  33.         for (int val = K; val <= 5000; val++) {
  34.             if (dp[val] <= 0) return true;
  35.         }
  36.         return false;
  37.     };
  38.  
  39.     ll lo = 0, hi = maxC, ans = maxC;
  40.     while (lo <= hi) {
  41.         ll mid = (lo + hi) / 2;
  42.         if (can(mid)) {
  43.             ans = mid;
  44.             hi = mid - 1;
  45.         } else {
  46.             lo = mid + 1;
  47.         }
  48.     }
  49.     cout << ans << "\n";
  50. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
5 10
1 1
2 2
3 3
4 4
5 5
stdout
copy 
3
https://ideone.com/LGbKps
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

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!