Submission #937841

#	Time	Username	Problem	Language	Result	Execution time	Memory
937841		duckindog	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	64 ms	6292 KiB

bridge

#include<bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10;
int k, n;
pair<int, int> a[N];

long long sum = 0;
priority_queue<int> lt;
priority_queue<int, vector<int>, greater<>> rt;
void rearrange() { 
  if (lt.top() <= rt.top()) return;
  int x = lt.top(), y = rt.top();
  lt.pop(), rt.pop();
  sum += 2 * x - 2 * y;
  lt.push(y); rt.push(x);
}
void clr() { 
  sum = 0;
  priority_queue<int> x;
  priority_queue<int, vector<int>, greater<>> y;
  swap(lt, x); swap(rt, y);
}
long long l[N], r[N];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);
  
  cin >> k >> n;
  long long add = 0;
  for (int i = 1; i <= n; ++i) { 
    char A, B;
    cin >> A >> a[i].first >> B >> a[i].second;
    if (A != B) continue;
    add += abs(a[i].first - a[i].second);
    i -= 1; n -= 1;
  }
  sort(a + 1, a + n + 1, [&](const auto& a, const auto& b) { 
    return a.first + a.second < b.first + b.second;
  });
  for (int i = 1; i <= n; ++i) { 
    int x, y; tie(x, y) = a[i];
    lt.push(x); rt.push(y);
    sum += y - x;
    rearrange();
    l[i] = sum;
  }
  if (k == 1) { 
    cout << l[n] + add + n;
    return 0;
  }

  clr();
  for (int i = n; i >= 1; --i) { 
    int x, y; tie(x, y) = a[i];
    lt.push(x); rt.push(y);
    sum += y - x;
    rearrange();
    r[i] = sum;
  }
  long long answer = l[n];
  for (int i = 2; i <= n; ++i) answer = min(answer, r[i] + l[i - 1]);
  
  cout << answer + add + n << "\n";
}

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