fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define ii pair<long long , int>
  10. #define lll pair<long long , pair<long long , long long>>
  11. #define lii pair<long long , pair<long long , int>>
  12. #define iii pair<int , pair<int , int>>
  13. #define iiii pair<pair<int , int> , pair<int , int>>
  14. #define llll pair<pair<__int128 , __int128> , pair<__int128 , __int128>>
  15. #define li pair<long long , int>
  16. #define db long double
  17. #define onBit(mask , i) (mask | (1 << i))
  18. #define offBit(mask , i) (mask & (~(1 << i)))
  19.  
  20. const long long INF = 1e16;
  21. const int N = 1e5 + 7;
  22. int n , X , Y , Z;
  23. long long BIT_val[N] , BIT_val_c[N] , A[N] , B[N];
  24. int BIT_id[N] , BIT_id_c[N] , c[N];
  25.  
  26. struct gv{
  27.     long long a , b , c , d;
  28. };
  29.  
  30. gv a[N];
  31.  
  32. bool cmp(gv x , gv y){
  33.     return x.d > y.d;
  34. }
  35.  
  36. struct gv1{
  37.     long long val;
  38.     int id;
  39. };
  40.  
  41. gv1 b[N];
  42.  
  43. bool cmp1(gv1 x , gv1 y){
  44.     return x.val < y.val;
  45. }
  46.  
  47. void update_id(int x , int val){
  48.     while (x <= n){
  49.         BIT_id[x] += val;
  50.         x += x & -x;
  51.     }
  52. }
  53.  
  54. int get_id(int x){
  55.     int res = 0;
  56.     while (x > 0){
  57.         res += BIT_id[x];
  58.         x -= x & -x;
  59.     }
  60.  
  61.     return res;
  62. }
  63.  
  64. void update_val(int x , long long val){
  65.     while (x <= n){
  66.         BIT_val[x] += val;
  67.         x += x & -x;
  68.     }
  69. }
  70.  
  71. long long get_val(int x){
  72.     long long res = 0;
  73.     while (x > 0){
  74.         res += BIT_val[x];
  75.         x -= x & -x;
  76.     }
  77.  
  78.     return res;
  79. }
  80.  
  81. void update_id_c(int x , int val){
  82.     while (x > 0){
  83.         BIT_id_c[x] += val;
  84.         x -= x & -x;
  85.     }
  86. }
  87.  
  88. int get_id_c(int x){
  89.     int res = 0;
  90.     while (x <= n){
  91.         res += BIT_id_c[x];
  92.         x += x & -x;
  93.     }
  94.  
  95.     return res;
  96. }
  97.  
  98. void update_val_c(int x , long long val){
  99.     while (x > 0){
  100.         BIT_val_c[x] += val;
  101.         x -= x & -x;
  102.     }
  103. }
  104.  
  105. long long get_val_c(int x){
  106.     long long res = 0;
  107.     while (x <= n){
  108.         res += BIT_val_c[x];
  109.         x += x & -x;
  110.     }
  111.  
  112.     return res;
  113. }
  114.  
  115. long long get_max(int k){
  116.     if (k == 0) return 0;
  117.     int l = 1 , r = n , mid , pos = 0;
  118.     while (l <= r){
  119.         mid = (l + r) >> 1;
  120.         if (get_id_c(mid) >= k){
  121.             pos = mid;
  122.             l = mid + 1;
  123.         }
  124.         else r = mid - 1;
  125.     }
  126.  
  127.     return get_val_c(pos);
  128. }
  129.  
  130. long long get_min(int k){
  131.     if (k == 0) return 0;
  132.     int l = 1 , r = n , mid , pos = 0;
  133.     while (l <= r){
  134.         mid = (l + r) >> 1;
  135.         if (get_id(mid) >= k){
  136.             pos = mid;
  137.             r = mid - 1;
  138.         }
  139.         else l = mid + 1;
  140.     }
  141.  
  142.     return get_val(pos);
  143. }
  144.  
  145. void ktao(){
  146.     for (int i = 1 ; i <= n ; ++i){
  147.         c[b[i].id] = i;
  148.     }
  149.  
  150.     for (int i = 1 ; i <= X ; ++i){
  151.         update_id_c(c[i] , 1);
  152.         update_val_c(c[i] , a[i].a);
  153.         update_id(c[i] , 1);
  154.         update_val(c[i] , a[i].c);
  155.     }
  156.     A[X] = get_max(X);
  157.     for (int i = X + 1 ; i <= n ; ++i){
  158.         update_id_c(c[i] , 1);
  159.         update_val_c(c[i] , a[i].a);
  160.         update_id(c[i] , 1);
  161.         update_val(c[i] , a[i].c);
  162.         A[i] = get_max(X) + get_min(i - X);
  163.     }
  164. }
  165.  
  166. void ktao1(){
  167.     memset(BIT_id , 0 , sizeof BIT_id);
  168.     memset(BIT_val , 0 , sizeof BIT_val);
  169.     memset(BIT_id_c , 0 , sizeof BIT_id_c);
  170.     memset(BIT_val_c , 0 , sizeof BIT_val_c);
  171.     for (int i = 1 ; i <= n ; ++i){
  172.         c[b[i].id] = i;
  173.     }
  174.  
  175.     for (int i = n ; i >= n - Y + 1 ; --i){
  176.         update_id_c(c[i] , 1);
  177.         update_val_c(c[i] , a[i].b);
  178.         update_id(c[i] , 1);
  179.         update_val(c[i] , a[i].c);
  180.     }
  181.     B[n - Y + 1] = get_max(Y);
  182.     for (int i = n - Y ; i >= 1 ; --i){
  183.         update_id_c(c[i] , 1);
  184.         update_val_c(c[i] , a[i].b);
  185.         update_id(c[i] , 1);
  186.         update_val(c[i] , a[i].c);
  187.         B[i] = get_max(Y) + get_min((n - i + 1) - Y);
  188.     }
  189. }
  190.  
  191. void inp(){
  192.     cin >> X >> Y >> Z;
  193.     n = X + Y + Z;
  194.     for (int i = 1 ; i <= n ; ++i){
  195.         cin >> a[i].a >> a[i].b >> a[i].c;
  196.         a[i].d = a[i].a - a[i].b;
  197.     }
  198.  
  199.     sort(a + 1 , a + n + 1, cmp);
  200.  
  201.     for (int i = 1 ; i <= n ; ++i){
  202.         b[i].val = a[i].a - a[i].c;
  203.         b[i].id = i;
  204.     }
  205.  
  206.     sort(b + 1 , b + n + 1 , cmp1);
  207.     ktao();
  208.  
  209.     for (int i = 1 ; i <= n ; ++i){
  210.         b[i].val = a[i].b - a[i].c;
  211.         b[i].id = i;
  212.     }
  213.  
  214.     sort(b + 1 , b + n + 1 , cmp1);
  215.     ktao1();
  216. }
  217.  
  218. void solve(){
  219.     long long res = -INF;
  220.     for (int i = X ; i <= n - Y ; ++i){
  221.         res = max(res , A[i] + B[i + 1]);
  222.     }
  223.  
  224.     cout << res;
  225. }
  226.  
  227. int main(){
  228. //    freopen("difmax.inp" , "r" , stdin);
  229. //    freopen("difmax.out" , "w" , stdout);
  230.     faster;
  231.     inp();
  232.     solve();
  233.     return 0;
  234. }
  235.  
Success #stdin #stdout 0.01s 7644KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RD4DfG
language:
C++14 (gcc 8.3)
created:
7 hours 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!