fork(2) download
copy 
  1. #include<iostream>
  2. #include<algorithm>
  3.  
  4. using namespace std;
  5.  
  6. int d,n,odp[100005];
  7.  
  8. pair <int,int> t[100005];//pierwszy koniec drugi poczatek
  9.  
  10. int Lower_bound(int L,int P,int w)
  11. {
  12.     if(L == P)
  13.         return L - 1;//celowo biore L - 1 zeby miec przedzial z wczesniejszym czasem zakonczenia
  14.     int S = (L + P) / 2;
  15.     if(t[S].first < w)
  16.         return Lower_bound(S + 1,P,w);
  17.     return Lower_bound(L,S,w);
  18. }
  19.  
  20. int algorytm(int k)
  21. {
  22.     for(int i = 0;i <= k; ++i)
  23.         odp[i] = 0;
  24.     for(int i = 1;i <= k; ++i)
  25.     {
  26.         int T = Lower_bound(1,n,t[i].second);
  27.         odp[i] = max(odp[i - 1],odp[T] + t[i].first - t[i].second);
  28.     }
  29.     return odp[k];
  30. }
  31.  
  32. int main()
  33. {
  34.     ios_base::sync_with_stdio(0);
  35.     cin.tie(NULL);
  36.     cin>>d;
  37.     for(int i = 0;i < d; ++i)
  38.     {
  39.         cin>>n;
  40.         for(int j = 1;j <= n; ++j)
  41.             cin>>t[j].second>>t[j].first;
  42.         sort(t,t + n);
  43.         cout<<algorytm(n)<<'\n';
  44.     }
  45.     return 0;
  46. }
Success #stdin #stdout 0s 16408KB
comments (?)
stdin
copy 
2
3
5 10
4 6
8 12
4
1 2
4 6
4 5
5 100
stdout
copy 
6
96
https://ideone.com/9qTJ85
language:
C++ (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!