Submission #241436

#	Time	Username	Problem	Language	Result	Execution time	Memory
241436		Nightlight	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	125 ms	6124 KiB

bridge

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

int K, N;
pii seg[100005];int p;
long long dpL[100005];//kalau prefix jadi 1 bagian
long long dpR[100005];//kalau suffix jadi 1 bagian
priority_queue<int, vector<int>, greater<int>> mn;long long sum_mn;
priority_queue<int, vector<int>> mx;long long sum_mx;
long long tot;
long long ans;

bool comp(pii A, pii B) {
  return A.first + A.second < B.first + B.second;
}

void clean() {
  while(!mn.empty()) {
//    cout << mn.top() << "\n";
    mn.pop();
  }
  while(!mx.empty()) {
//    cout << mx.top() << "\n";
    mx.pop();
  }
  sum_mn = 0;
  sum_mx = 0;
  tot = 0;
}

long long balance() {
  while(mn.size() > tot / 2) {
    int now = mn.top();
    mn.pop();
    sum_mn -= now;
    mx.emplace(now);
    sum_mx += now;
  }
  while(mx.size() > tot / 2) {
    int now = mx.top();
    mx.pop();
    sum_mx -= now;
    mn.emplace(now);
    sum_mn += now;
  }
  while(mn.top() < mx.top()) {
    int sm = mn.top(), bg = mx.top();
    mn.pop(), mx.pop();
    mn.emplace(bg);
    mx.emplace(sm);
    sum_mn += bg - sm;
    sum_mx += sm - bg;
  }
//  cout << sum_mn << " " << sum_mx << "\n";
  return sum_mn - sum_mx;
}

long long adds(int idx) {
  mn.emplace(seg[idx].first);
  mn.emplace(seg[idx].second);
  sum_mn += seg[idx].first + seg[idx].second;
  tot += 2;
  return balance();
}

void solve() {
  for(int i = 1; i <= p; i++) {
    dpL[i] = adds(i);
  }
  if(K == 1) {
    printf("%lld\n", dpL[p] + ans + tot / 2);
    return;
  }
  clean();
  long long res = dpL[p];
  for(int i = p; i > 0; i--) {
    dpR[i] = adds(i);
    res = min(res, dpL[i - 1] + dpR[i]);
  }
  printf("%lld\n", res + ans + tot / 2);
}

int main() {
  ios_base::sync_with_stdio(0);
  cin >> K >> N;
  int S, E;char a, b;
  for(int i = 1; i <= N; i++) {
    cin >> a >> S >> b >> E;
    if(a == b) {
      ans += abs(S - E);
    }else {
      seg[++p] = make_pair(S, E);
    }
  }
  sort(seg + 1, seg + p + 1, comp);
//  for(int i = 1; i <= p; i++) cout << seg[i].first << " " << seg[i].second << " ";
  cout << "\n";
  solve();
  cin >> N;
}

Compilation message (stderr)

bridge.cpp: In function 'long long int balance()':
bridge.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(mn.size() > tot / 2) {
         ~~~~~~~~~~^~~~~~~~~
bridge.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(mx.size() > tot / 2) {
         ~~~~~~~~~~^~~~~~~~~

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