fork download
copy 
  1. //@author :: Abhimanyu Chauhan (sheer will nothing else ...)
  2.  
  3. #include<bits/stdc++.h>
  4.  
  5.  
  6. #define f			first
  7. #define sz(a)  ((int)(a).size())
  8. #define s			second
  9. #define present(c,x) ((c).find(x)!=(c).end())
  10. #define all(v)		v.begin(),v.end()
  11. #define pii 			pair<int,int>
  12. #define pil 		pair<int,long long>
  13. #define pll 		pair<long long , long long>
  14. #define vpii 		vector<pii>
  15. #define vpil 		vector<pil>
  16. #define vpll 		vector<pll>
  17. #define eb			emplace_back
  18. #define mem(x) 			memset(x , 0 , sizeof(x))
  19. #define pb			push_back
  20. #define fo(i,n)		for(int i=0;i<n;i++)
  21. #define Fo(i,k,n)	for(int i=k;i<n;i++)
  22. #define vi			vector<int>
  23. #define vll			vector<ll>
  24. #define deb(x)		cout << #x << " " << x << endl
  25.  
  26. using namespace std;
  27. using ll  = long long;
  28. using lld = long double;
  29. using l64 = int64_t;
  30.  
  31. const int oo = 0x3f3f3f3f;
  32. const ll MOD = 1000000007;
  33. #define ar array<int,3>
  34.  
  35. //deadline -> 2
  36. //duration -> 1
  37. //reward -> 0
  38.  
  39. const int N = 1001;
  40. int dp[N][N * 102];
  41. int n , t;
  42. vector<ar> jobs(N);
  43.  
  44. int fun(int i , int j){
  45.     if(i == n)
  46.         return 0;
  47.  
  48.     auto &res = dp[i][j];
  49.     if(res != -1)
  50.         return res;
  51.  
  52.     //at ith job , have choice to take up this job or reject it
  53.     int ans = 0;
  54.  
  55.     //can take this job only when this is true
  56.     if(jobs[i][1] + j <= min(jobs[i][2] , t))
  57.         ans = jobs[i][0] + fun(i + 1 , j + jobs[i][1]);
  58.  
  59.     // leave this job , move to next without changing the time j 
  60.     ans = max(ans , fun(i + 1 , j));
  61.     return res = ans;
  62. }
  63.  
  64. signed main(){
  65.  
  66. #ifndef ONLINE_JUDGE 
  67. //    freopen("in.txt","r",stdin);
  68. #endif
  69.     memset(dp , -1 , sizeof(dp));
  70.     ios_base::sync_with_stdio(0);cin.tie(0);
  71.  
  72.     cin >> t >> n;
  73.     fo(j , 3)
  74.         fo(i , n)
  75.             cin >> jobs[i][j];
  76.  
  77.     sort(jobs.begin() , jobs.begin() + n , [&](const ar &a ,const ar &b){
  78.             if(a[2] != b[2])
  79.                 return a[2] < b[2];
  80.             return a < b;
  81.     });
  82.  
  83.     cout << fun(0 , 0) << "\n";
  84.     return 0;
  85. }
  86.  
Success #stdin #stdout 0.1s 402960KB
comments (?)
stdin
copy 
20 5
4 3 2 5 4
7 6 4 6 6
9 13 12 13 20
stdout
copy 
13
https://ideone.com/AjY0Yt
language:
C++14 (gcc 8.3)
created:
5 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!