nicuvlad76

Untitled

Nov 6th, 2018
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.82 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5.  
  6. ifstream fin ("credite.in");
  7. ofstream fout ("credite.out");
  8.  
  9.  
  10. int dp[2][10005] , n;
  11.  
  12.  
  13. struct D
  14. {
  15. int val , timp;
  16. };
  17.  
  18. D a[10005];
  19.  
  20.  
  21. inline bool CMP(const D A , const D B)
  22. {
  23. return A . timp < B . timp;
  24. }
  25.  
  26.  
  27. int main()
  28. {
  29. int lin = 0 , mx = 0;
  30. fin >> n;
  31. for(int i = 1 ; i <= n ; i++)
  32. fin >> a[i] . val >> a[i] . timp;
  33. sort(a + 1 , a + n + 1 , CMP);
  34. for(int i = 1 ; i <= n ; i++)
  35. {
  36. lin = 1 - lin;
  37. for(int j = 1 ; j <= a[i] . timp ; j++)
  38. dp[lin][j] = max(dp[1 - lin][j - 1] + a[i] . val , dp[1 - lin][j]);
  39. }
  40. mx = 0;
  41. for(int i = 1 ; i <= a[n] . timp ; i++)
  42. mx = max(mx , dp[lin][i]);
  43. fout << mx << "\n";
  44. fin.close();
  45. fout.close();
  46. return 0;
  47. }
Add Comment
Please, Sign In to add comment