oj.uz

Submission #853709

# Submission time Handle Problem Language Result Execution time Memory
853709 2023-09-25T04:58:45 Z NeroZein Palembang Bridges (APIO15_bridge) C++17
100 / 100
 153 ms 14288 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

multiset<int> lo, hi; 
long long sum1, sum2; 

void fix() {
  if (lo.size() > hi.size() + 1) {
    int tmp = *lo.rbegin();
    sum1 -= tmp;
    lo.erase(lo.find(tmp)); 
    sum2 += tmp; 
    hi.insert(tmp); 
  } 
  if (hi.size() > lo.size()) {
    int tmp = *hi.begin();
    sum2 -= tmp; 
    hi.erase(hi.find(tmp));
    sum1 += tmp; 
    lo.insert(tmp); 
  }
}

void ins(int x) {
  if (!lo.empty() && x >= *lo.rbegin()) {
    sum2 += x;
    hi.insert(x);
  } else {
    sum1 += x; 
    lo.insert(x); 
  }
  fix(); 
}

long long get() {
  int med = *lo.rbegin();
  int sz1 = lo.size(), sz2 = hi.size();
  long long ret = (long long) med * sz1 - sum1 + sum2 - (long long) med * sz2;
  return ret;
}

void clear() {
  lo.clear();
  hi.clear();
  sum1 = sum2 = 0; 
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int k, n;
  cin >> k >> n;
  long long ans = 0; 
  vector<pair<int,int>> vec; 
  for (int i = 0; i < n; ++i) {
    char z, z2;
    int x, x2;
    cin >> z >> x >> z2 >> x2;
    //if (x > x2) swap(x, x2); important for proof only
    if (z == z2) {
      ans += abs(x - x2); 
    } else {
      vec.emplace_back(x, x2); 
    }
  }
  if (!vec.size()) {
    cout << ans << '\n';
    return 0; 
  }
  n = vec.size();
  ans += n; 
  sort(vec.begin(), vec.end(), [](pair<int, int> i, pair<int, int> j) {
    return i.first + i.second < j.first + j.second; 
  });
  deb(vec); cout << '\n';
  vector<long long> pref(n); 
  for (int i = 0; i < n; ++i) {
    ins(vec[i].first);
    ins(vec[i].second);
    pref[i] = get(); 
  }
  clear(); 
  vector<long long> suf(n);
  for (int i = n - 1; i >= 0; --i) {
    ins(vec[i].first);
    ins(vec[i].second);
    suf[i] = get(); 
  }
  long long res = ans + pref.back();
  if (k == 2) {
    for (int i = 0; i < n - 1; ++i) {
      res = min(res, ans + pref[i] + suf[i + 1]); 
    }
  }
  cout << res << '\n'; 
  return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 544 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 105 ms 12136 KB Output is correct
13 Correct 142 ms 11976 KB Output is correct
14 Correct 136 ms 10956 KB Output is correct
15 Correct 80 ms 7120 KB Output is correct
16 Correct 108 ms 12028 KB Output is correct
17 Correct 102 ms 11980 KB Output is correct
18 Correct 81 ms 11980 KB Output is correct
19 Correct 118 ms 12060 KB Output is correct
20 Correct 109 ms 11972 KB Output is correct
21 Correct 112 ms 12176 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 2 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 2 ms 344 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 1 ms 344 KB Output is correct
24 Correct 1 ms 344 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 107 ms 12956 KB Output is correct
26 Correct 139 ms 12992 KB Output is correct
27 Correct 148 ms 13868 KB Output is correct
28 Correct 153 ms 14280 KB Output is correct
29 Correct 152 ms 14284 KB Output is correct
30 Correct 71 ms 7888 KB Output is correct
31 Correct 115 ms 13768 KB Output is correct
32 Correct 105 ms 14280 KB Output is correct
33 Correct 82 ms 14132 KB Output is correct
34 Correct 107 ms 14288 KB Output is correct
35 Correct 112 ms 14028 KB Output is correct
36 Correct 115 ms 14212 KB Output is correct
37 Correct 110 ms 12740 KB Output is correct