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. 	{
  14.     	if(t[L].first == w)
  15.     		return L;
  16.     	else
  17.         	return L - 1;
  18. 	}
  19.     int S = (L + P) / 2;
  20.     if(t[S].first < w)
  21.         return Lower_bound(S + 1,P,w);
  22.     return Lower_bound(L,S,w);
  23. }
  24.  
  25. int algorytm(int k)
  26. {
  27.     for(int i = 0;i <= k; ++i)
  28.         odp[i] = 0;
  29.     for(int i = 1;i <= k; ++i)
  30.     {
  31.         int T = Lower_bound(1,n,t[i].second);
  32.         odp[i] = max(odp[i - 1],odp[T] + t[i].first - t[i].second);
  33.     }
  34.     return odp[k];
  35. }
  36.  
  37. int main()
  38. {
  39.     ios_base::sync_with_stdio(0);
  40.     cin.tie(NULL);
  41.     cin>>d;
  42.     for(int i = 0;i < d; ++i)
  43.     {
  44.         cin>>n;
  45.         for(int j = 1;j <= n; ++j)
  46.             cin>>t[j].second>>t[j].first;
  47.         sort(t + 1,t + (n + 1));
  48.         cout<<algorytm(n)<<'\n';
  49.     }
  50.     return 0;
  51. }
Success #stdin #stdout 0s 16408KB
comments (?)
stdin
copy 
1
3
9 12
8 12
5 7
stdout
copy 
6
https://ideone.com/owX1RL
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!