Mehulcoder

CureFit A

Oct 4th, 2020 (edited)
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.84 KB | None | 0 0
  1. /*
  2. Author: Mehul Chaturvedi
  3. */
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. using ll = long long;
  9. using ld = long double;
  10. using pll = pair<ll, ll>;
  11.  
  12. #define mp make_pair
  13. #define all(x) (x).begin(), (x).end()
  14. #define f first
  15. #define s second
  16. #define vll vector<long long>
  17. #define vvll vector<vector<ll>>
  18. #define vset(v, n, val) v.clear(); v.resize(n, val)
  19. #define INF 4557430888798830399ll
  20. #define fr(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
  21. #define rep(i, n) for (int i = 0, _n = (n); i < _n; i++)
  22. #define repr(i, n) for (int i = n; i >= 0; i--)
  23. #define frr(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
  24. #define trav(a, x) for(auto& a : x)
  25. #define fil(ar, val) memset(ar, val, sizeof(ar))
  26. const ll MOD = 1e9 + 7;
  27.  
  28.  
  29. vvll times;
  30. vll dp;
  31. ll n;
  32. bool mySort(vll &a, vll &b) {
  33.     return (a[0] < b[0]);
  34. }
  35.  
  36. ll getInd(ll minStart, ll indStart) {
  37.     ll lo = indStart;
  38.     ll hi = n - 1;
  39.  
  40.     ll ans = -1;
  41.     while (lo <= hi) {
  42.         ll mid = (lo + hi) / 2;
  43.         if (times[mid][0] >= minStart) {
  44.             hi = mid - 1;
  45.             ans = mid;
  46.         } else {
  47.             lo = mid + 1;
  48.         }
  49.     }
  50.  
  51.     return ans;
  52. }
  53.  
  54. ll get(ll startInd) {
  55.     if (startInd == n) return 0;
  56.  
  57.     ll &anss = dp[startInd];
  58.     if (anss != -1) return anss;
  59.  
  60.     ll ans = times[startInd][2];
  61.     ll ending = times[startInd][1];
  62.     ll ind2 = getInd(ending, startInd + 1);
  63.  
  64.     if (ind2 != -1) {
  65.         ans += get(ind2);
  66.     }
  67.  
  68.  
  69.     ll ans2 = get(startInd + 1);
  70.     return anss = max(ans, ans2);
  71. }
  72.  
  73. void solve() {
  74.     cin >> n;
  75.     vset(times, n, vll(3, -1));
  76.     vset(dp, n + 10, -1);
  77.  
  78.     rep(i, n) cin >> times[i][0];
  79.     rep(i, n) cin >> times[i][1];
  80.     rep(i, n) cin >> times[i][2];
  81.  
  82.     sort(all(times), mySort);
  83.  
  84.     ll ans = get(0);
  85.  
  86.     cout << ans << '\n';
  87.     return;
  88. }
  89.  
  90. int main(int argc , char ** argv) {
  91.     ios_base::sync_with_stdio(false) ;
  92.     cin.tie(NULL) ;
  93.  
  94.     ll t = 1;
  95.     while (t--) {
  96.         solve();
  97.     }
  98.  
  99.     return 0 ;
  100. }
Add Comment
Please, Sign In to add comment