Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- long check(vector <pair <int, int> > v, int pos) {
- long ans;
- int fl = v[pos].first;
- for (int i = pos - 1; i >= 0; i--) {
- ans += v[i].second * (fl - (v[i].first + v[i].second));
- fl -= v[i].second;
- }
- fl = v[pos].first + v[pos].second - 1;
- for (int i = pos + 1; i < (int) v.size(); i++) {
- ans += (v[i].first - fl - 1) * v[i].second;
- fl += v[i].second;
- }
- return ans;
- }
- long minimumTotalPower(vector<int> treasureBoxes, int k) {
- vector <pair <int, int> > v;
- int n = treasureBoxes.size();
- bool fl = false;
- int st = 0;
- for (int i = 1; i < n; i++) {
- if (treasureBoxes[i] != treasureBoxes[i - 1]) {
- if (treasureBoxes[i - 1] == 1) {
- v.push_back(make_pair(st, i - st));
- } else {
- st = i;
- }
- }
- }
- if (treasureBoxes[n - 1] == 1) {
- v.push_back(make_pair(st, n - st));
- }
- int m = v.size();
- if (m == 0) {
- return 0;
- }
- long ans = 100000000000000;
- for (int i = 0; i < m; i++) {
- ans = min(ans, check(v, i));
- }
- return ans * k;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement