Advertisement
Guest User

Untitled

a guest
Aug 20th, 2019
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.24 KB | None | 0 0
  1. long check(vector <pair <int, int> > v, int pos) {
  2.     long ans;
  3.    
  4.     int fl = v[pos].first;
  5.    
  6.     for (int i = pos - 1; i >= 0; i--) {
  7.         ans += v[i].second * (fl - (v[i].first + v[i].second));
  8.         fl -= v[i].second;
  9.     }
  10.    
  11.     fl = v[pos].first + v[pos].second - 1;
  12.    
  13.     for (int i = pos + 1; i < (int) v.size(); i++) {
  14.         ans += (v[i].first - fl - 1) * v[i].second;
  15.         fl += v[i].second;
  16.     }
  17.    
  18.     return ans;
  19. }
  20.  
  21. long minimumTotalPower(vector<int> treasureBoxes, int k) {
  22.     vector <pair <int, int> > v;
  23.    
  24.     int n = treasureBoxes.size();
  25.    
  26.     bool fl = false;
  27.     int st = 0;
  28.    
  29.     for (int i = 1; i < n; i++) {
  30.         if (treasureBoxes[i] != treasureBoxes[i - 1]) {
  31.             if (treasureBoxes[i - 1] == 1) {
  32.                 v.push_back(make_pair(st, i - st));
  33.             } else {
  34.                 st = i;
  35.             }
  36.         }
  37.     }
  38.    
  39.     if (treasureBoxes[n - 1] == 1) {
  40.         v.push_back(make_pair(st, n - st));
  41.     }
  42.    
  43.     int m = v.size();
  44.    
  45.     if (m == 0) {
  46.         return 0;
  47.     }
  48.    
  49.     long ans = 100000000000000;
  50.    
  51.     for (int i = 0; i < m; i++) {
  52.         ans = min(ans, check(v, i));
  53.     }
  54.    
  55.     return ans * k;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement