fork download
copy 
  1. // Author: Pawan Raj
  2.  
  3. #include <bits/stdc++.h>
  4. #define fi first
  5. #define se second
  6. #define pb push_back
  7. #define int long long
  8. #define F(i, n) for (int i = 0; i < n; i++)
  9. #define all(x) (x).begin(), (x).end()
  10.  
  11. using namespace std;
  12. using ld = long double;
  13. using vi = vector<int>;
  14. using mi = map<int, int>;
  15. using pi = pair<int, int>;
  16.  
  17. const int N = 1e6 + 5;
  18. const int MOD = 1e9 + 7;
  19. const int inf = 1e18 + 1;
  20. /***************************code begins here*****************************/
  21.  
  22. void solve() {
  23.     int h, n, ans = 0;
  24.     cin >> h >> n;
  25.  
  26.     assert(1 <= h && h <= 1e4);
  27.     assert(1 <= n && n <= 1e3);
  28.  
  29.     vi a(n), b(n);
  30.  
  31.     F(i, n) {
  32.         cin >> a[i] >> b[i];
  33.         assert(1 <= a[i] && a[i] <= 1e4);
  34.         assert(1 <= b[i] && b[i] <= 1e4);
  35.     }
  36.  
  37.     vector<int> dp(h + 1, inf);
  38.  
  39.     dp[0] = 0;
  40.  
  41.     F(i, n) {
  42.         for (int j = 0; j <= h; j++) {
  43.             int k = min(j + a[i], h);
  44.             dp[k] = min(dp[k], dp[j] + b[i]);
  45.         }
  46.     }
  47.  
  48.     ans = dp[h];
  49.  
  50.     cout << ans << '\n';
  51. }
  52.  
  53. int32_t main() {
  54.     ios::sync_with_stdio(false);
  55.     cin.tie(0);
  56.     cout.tie(0);
  57.  
  58.     int t = 1;
  59.     // cin >> t;
  60.     // assert(1 <= t && t <= 5);
  61.  
  62.     while (t--) {
  63.         solve();
  64.     }
  65.  
  66.     return 0;
  67. }
Success #stdin #stdout 0s 5544KB
comments (?)
stdin
copy 
9 3
2 1
4 2
8 3
stdout
copy 
4
https://ideone.com/8Qqqac
language:
C++14 (gcc 8.3)
created:
2 years 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!