Submission #242943

#	Time	Username	Problem	Language	Result	Execution time	Memory
242943		neihcr7j	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	387 ms	15312 KiB

bridge

#include<bits/stdc++.h>

#define oo ll(1e15)
#define maxn 100005

using namespace std;
typedef long long ll;

ll n, k;
vector < pair < ll, ll > > L;

ll a[maxn], b[maxn];

void calc(vector < pair < ll, ll > >& L, ll a[]){
  multiset < ll > s, tem;
  s.clear(); tem.clear();

  ll sum = 0, ret = 0;

  a[0] = 0;
  for (ll i = 1; i <= n; ++i) {
    ll x = L[i - 1].first, y = L[i - 1].second;

    sum += x + y;
    s.insert(x); ret += x;
    s.insert(y); ret += y;

    while (s.size() > i) {
      ret -= *s.begin();
      tem.insert(-(*s.begin()));
      s.erase(s.begin());
    }

    while (-(*tem.begin()) > *s.begin()) {
      ret -= *tem.begin() + *s.begin();
      ll tg = -*tem.begin();
      tem.erase(tem.begin());
      tem.insert(-*s.begin());
      s.erase(s.begin());
      s.insert(tg);
    }

    a[i] = 2 * ret - sum;
  }
}

int main(){
  #define TASK "ABC"
 // freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout);
  ios_base::sync_with_stdio(0);

  ll ret = 0;

  cin >> k >> n;

  for (ll i = 0; i < n; ++i) {
    char ch1, ch2;
    ll x, y;
    cin >> ch1 >> x >> ch2 >> y;

    if (x > y) swap(x, y);

    if (ch1 == ch2) {
      ret += y - x;
      continue;
    }

    L.push_back({x, y});
  }

  n = L.size();

  sort(L.begin(), L.end(), [](pair < ll, ll > i, pair < ll, ll > j){
    return i.first + i.second < j.first + j.second;
  });

  calc(L, a);
  reverse(L.begin(), L.end());
  calc(L, b);

  ll ans = a[n] + ret + n;

  if (k == 1)
    cout << ans;
  else {
    for (ll i = 1; i < n; ++i) {
   //   cerr << i << ' ' << b[4] << '\n';
      ans = min(ans, a[i] + b[n - i] + ret + n);
    }
    cout << ans;
  }

  return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'void calc(std::vector<std::pair<long long int, long long int> >&, ll*)':
bridge.cpp:28:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (s.size() > i) {
            ~~~~~~~~~^~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37