ismaeil

K. Competitions

May 25th, 2021 (edited)
208
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.73 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef vector< ll > vl;
  6.  
  7. vector< vl > dp;
  8. vector< vl > v;
  9. int n;
  10.  
  11. inline bool cmp(const vl &a ,const vl &b)
  12. {
  13.     return a[0] < b[0];
  14. }
  15.  
  16. void init()
  17. {
  18.     dp.assign(n + 1 ,vl(5 ,0));
  19.     v.assign(n + 1 ,vl(4 ,INT_MAX));
  20.    
  21.     dp[n][3] = -1;
  22.     dp[n][4] = -1;
  23.  
  24. /// --- State of main vector --- ///
  25. /// v[i][0] = L
  26. /// v[i][1] = R
  27. /// v[i][2] = C
  28. /// v[i][3] = Idx
  29.  
  30. /// --- State of dp vector --- ///
  31. /// dp[i][0] = cnt
  32. /// dp[i][1] = score
  33. /// dp[i][2] = dur
  34. /// dp[i][3] = par
  35. /// dp[i][4] = ref
  36. }
  37.  
  38. int lowerBound(int L ,int R ,ll val)
  39. {
  40.     while( L < R - 1 )
  41.     {
  42.         int Mid = (L + R) >> 1;
  43.        
  44.         v[Mid][0] >= val ? R = Mid : L = Mid;
  45.     }
  46.    
  47.     return v[L][0] >= val ? L : R;
  48. }
  49.  
  50. int main()
  51. {
  52.     scanf("%d" ,&n);  init();
  53.    
  54.     for(int i = 0 ; i < n ; i++)
  55.     {
  56.         scanf("%lld" ,&v[i][0]);
  57.         scanf("%lld" ,&v[i][1]);
  58.         scanf("%lld" ,&v[i][2]);
  59.         v[i][3] = i + 1;
  60.     }
  61.    
  62.     sort(v.begin() ,v.begin() + n ,cmp);
  63.    
  64.     for(int i = n - 1 ; i >= 0 ; i--)
  65.     {
  66.         int j = lowerBound(i + 1 ,n ,v[i][1]);
  67.        
  68.         dp[i][3] = j;
  69.         dp[i][4] = -1;
  70.         dp[i][0] = dp[j][0] + 1;
  71.         dp[i][1] = dp[j][1] + v[i][2];
  72.         dp[i][2] = dp[j][2] + v[i][1] - v[i][0];
  73.        
  74.         if( dp[i][1] == dp[i + 1][1] )
  75.         {
  76.             if( dp[i][2] > dp[i + 1][2] )
  77.             {
  78.                 dp[i] = dp[i + 1];
  79.                 dp[i][3] = -1;
  80.                 dp[i][4] = i + 1;
  81.             }
  82.         }
  83.         else if( dp[i][1] < dp[i + 1][1] )
  84.         {
  85.             dp[i] = dp[i + 1];
  86.             dp[i][3] = -1;
  87.             dp[i][4] = i + 1;
  88.         }
  89.     }
  90.    
  91.     int i = 0;
  92.     printf("%lld %lld %lld\n" ,dp[i][0] ,dp[i][1] ,dp[i][2]);
  93.    
  94.     while( dp[i][3] != -1 || dp[i][4] != -1 )
  95.     {
  96.         if( dp[i][3] != -1 )
  97.         {
  98.             printf("%lld " ,v[i][3]);
  99.             i = dp[i][3];
  100.         }
  101.         else i = dp[i][4];
  102.     }
  103.    
  104.     return 0;
  105. }
  106.  
Add Comment
Please, Sign In to add comment