fork download
copy 
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <queue>
  4. #include <vector>
  5. #include <map>
  6. #include <set>
  7. #include <stdio.h>
  8. #include <math.h>
  9.  
  10. using namespace std;
  11.  
  12. #define MAX_N 100010
  13.  
  14. long long my_abs(long long a)
  15. {
  16. 	return a > 0 ? a : -a;
  17. }
  18.  
  19. struct element {
  20.     int left;
  21.     int right;
  22.     long long weight;
  23. };
  24.  
  25. element e_array[MAX_N + 5];
  26.  
  27. void element_erase(int idx) {
  28.     if(idx < 0) {
  29.         return ;
  30.     }
  31.     int left = e_array[idx].left;
  32.     int right = e_array[idx].right;
  33.     if(left >= 0) {
  34.         e_array[left].right = right;
  35.     }
  36.     if(right >= 0) {
  37.         e_array[right].left = left;
  38.     }
  39.     return ;
  40. }
  41.  
  42. int main()
  43. {
  44.     int N;
  45.     int M;
  46.     long long val, pre_val;
  47.     int real_cnt = 0;
  48.     long long sub_sum = 0;
  49.     long long tot_sum = 0;
  50.     set<pair<long long, int> > heap;
  51.     int cnt = 0;
  52.  
  53.     scanf("%d%d", &N, &M);
  54.  
  55.     //scanf("%I64d", &pre_val);
  56.     for(int i = 0; i < N; ++i) {
  57.         //val = pre_val;
  58.         //scanf("%I64d", &pre_val);
  59.         //val = pre_val - val;
  60.         scanf("%d", &val);
  61.         if((val < 0 && sub_sum > 0) || (val > 0 && sub_sum < 0)) {   
  62.             if(sub_sum >= 0) {
  63.                 ++real_cnt;
  64.             }
  65.             if(cnt > 0 || sub_sum > 0) {
  66.                 e_array[cnt].left = cnt - 1;
  67.                 e_array[cnt].weight = sub_sum;
  68.                 e_array[cnt].right = cnt + 1;
  69.                 ++cnt;
  70.             }
  71.             sub_sum = 0;
  72.         }
  73.         sub_sum += val;
  74.         tot_sum += val > 0 ? val : 0;
  75.     }
  76.  
  77.     if(sub_sum > 0) {
  78.         e_array[cnt].left = cnt - 1;
  79.         e_array[cnt].weight = sub_sum;
  80.         e_array[cnt].right = -1;
  81. 		++cnt;
  82. 		++real_cnt;
  83.     }
  84.     e_array[cnt - 1].right = -1;
  85.  
  86.     for(int i = 0; i < cnt; ++i) {
  87.     	heap.insert(pair<long long, int>(my_abs(e_array[i].weight), i));
  88.     }
  89.  
  90.     for(; M < real_cnt; ++M) {
  91.         set<pair<long long, int> >::iterator h_it = heap.begin();
  92.         int w_idx = h_it->second;
  93.         int w_idx_left = e_array[w_idx].left;
  94.         int w_idx_right = e_array[w_idx].right;
  95.  
  96.         long long w = 0;
  97.         tot_sum -= h_it->first;
  98.         int flag = 0;
  99.  
  100.         if(w_idx_left != -1) {
  101.         	w += my_abs(e_array[w_idx_left].weight);
  102. 			heap.erase(pair<long long, int>(my_abs(e_array[w_idx_left].weight), w_idx_left));
  103.         	element_erase(w_idx_left);
  104.         } else {
  105.         	flag = 1;
  106.         }
  107. 	    if(w_idx_right != -1) {
  108.         	w += my_abs(e_array[w_idx_right].weight);
  109. 	    	heap.erase(pair<long long, int>(my_abs(e_array[w_idx_right].weight), w_idx_right));
  110.         	element_erase(w_idx_right);
  111. 	    } else {
  112.         	flag = 1;
  113.         }
  114.  
  115.         w -= my_abs(e_array[w_idx].weight);
  116.  
  117.         if(e_array[w_idx].weight > 0 && flag == 1) {
  118.         	element_erase(w_idx);
  119.         } else {
  120.         	heap.insert(pair<long long, int>(w, w_idx));
  121.         	e_array[w_idx].weight = w;
  122.         }
  123.         heap.erase(h_it);
  124.     }
  125.     cout << tot_sum << endl;
  126.  	return 0;   
  127. }
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
Success #stdin #stdout 0s 4996KB
comments (?)
stdin
copy 
7 2
-2
11
-4
13
-5
6
-2
stdout
copy 
-7975854517503655937
https://ideone.com/7hO7AT
language:
C++14 (gcc 8.3)
created:
9 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!