fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. struct Inter {
  6.     double left;
  7.     double right;
  8.     double weight;
  9. };
  10.  
  11. int p(std::vector<Inter>& v, int j) {
  12.     int temp = -1;
  13.     int l = 0;
  14.     int r = j;
  15.     while (l != r) {
  16.         if (v[(l+r)/2].right <= v[j].left && r - l > 1) {
  17.             temp = (l+r)/2;
  18.             l = (l+r)/2;
  19.         } else {
  20.             if (v[(l+r)/2].right <= v[j].left)
  21.                 temp = (l+r)/2;
  22.             r = (l+r)/2;
  23.         }
  24.     }
  25.     return temp;
  26. }
  27.  
  28. double opt(std::vector<Inter>& v, int j) {
  29.     std::vector<double> M(j+2);
  30.     M[0] = 0;
  31.     for (int i = 1; i <= j+1; ++i) {
  32.         M[i] = std::max(v[i-1].weight + M[p(v, i - 1) + 1], M[i-1]);
  33.     }
  34.     return M[j+1];
  35. }
  36.  
  37. bool compare(Inter& a, Inter& b) {
  38.     return a.right < b.right;
  39. }
  40.  
  41. int main() {
  42.     int n;
  43.     std::cin >> n;
  44.     double l, r, w;
  45.     Inter inter;
  46.     std::vector<Inter> v(n);
  47.     for (int i = 0; i < n; ++i) {
  48.         std::cin >> inter.left >> inter.right >> inter.weight;
  49.         v[i] = inter;
  50.     }
  51.     std::sort(v.begin(), v.end(), compare);
  52.     std::cout << opt(v, n-1);
  53. }
  54.  
  55.  
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
3
1 2 1
0 1 1
0.5 1.5 1.5
stdout
copy 
2
https://ideone.com/ynVqej
language:
C++14 (gcc 8.3)
created:
6 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!