fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. struct range {
  6.   int from, to;
  7.   double w;
  8. };
  9. bool operator<(range const& l, range const& r) { return l.to < r.to; }
  10.  
  11. struct until_now {
  12.   until_now(int pos, double w) : pos(pos), w(w) {}
  13.   int pos;
  14.   double w;
  15. };
  16. bool operator<(until_now const& l, int pos) { return l.pos > pos; }
  17.  
  18. int main()
  19. {
  20.   std::vector<range> ranges;
  21.   for (range r; std::cin >> r.from >> r.to >> r.w;)
  22.     ranges.push_back(r);
  23.   std::sort(ranges.begin(), ranges.end());
  24.  
  25.   std::vector<until_now> dp; dp.push_back(until_now(-1, 0));
  26.   for (std::vector<range>::const_iterator it=ranges.begin(); it!=ranges.end(); ++it) {
  27.     double w = std::max(dp.back().w,
  28.                         std::lower_bound(dp.rbegin(), dp.rend(), it->from)->w + it->w);
  29.     if (dp.back().pos == it->to) dp.back().w = std::max(dp.back().w, w);
  30.     else dp.push_back(until_now(it->to, w));
  31.   }
  32.   std::cout << dp.back().w << '\n';
  33. }
  34.  
Success #stdin #stdout 0s 2868KB
comments (?)
stdin
copy 
1 3 0.5
2 5 0.2
2 7 0.4
4 7 0.3
6 9 0.1
stdout
copy 
0.8
https://ideone.com/tsWU9O
language:
C++ 4.3.2 (gcc-4.3.2)
created:
12 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!