fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define all(v) v.begin() , v.end()
  5. #define sz(v) int(v.size())
  6. #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef pair<int , int> ii;
  11. typedef pair<long long , int> lli;
  12.  
  13. const int maxN = 3007;
  14. const ll inf = ll(1e18)+7;
  15.  
  16. int n , t[maxN] , f[maxN];
  17. ll dp[maxN][maxN];
  18.  
  19. void solve(){
  20.     cin >> n;
  21.     for (int i = 1 ; i <= n ; i++) cin >> t[i];
  22.     for (int i = 1 ; i <= n ; i++) cin >> f[i];
  23.     for (int i = 0 ; i <= n ; i++){
  24.         for (int j = 0 ; j <= n ; j++) dp[i][j] = inf;
  25.     }
  26.     dp[0][0] = 0;
  27.     for (int i = 1 ; i <= n ; i++){
  28.         for (int j = 0 ; j <= n ; j++) dp[i][j] = dp[i - 1][j];
  29.         for (int j = 1 ; j <= n ; j++){
  30.             if (dp[i - 1][j - 1] <= t[i]){
  31.                 dp[i][j] = min(dp[i][j] , dp[i - 1][j - 1] + f[i]);
  32.             }
  33.         }
  34.     }
  35.     for (int i = n ; i >= 0 ; i--){
  36.         if (dp[n][i] != inf){
  37.             cout << i << "\n";
  38.             return;
  39.         }
  40.     }
  41. }
  42.  
  43. #define name "A"
  44.  
  45. int main(){
  46.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  47.     if (fopen(name".INP" , "r")){
  48.         freopen(name".INP" , "r" , stdin);
  49.         freopen(name".OUT" , "w" , stdout);
  50.     }
  51.     int t = 1; //cin >> t;
  52.     while (t--) solve();
  53.     return 0;
  54. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/K1u3Tg
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!