Submission #962848

#	Time	Username	Problem	Language	Result	Execution time	Memory
962848		zNatsumi	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	90 ms	8064 KiB

bridge

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int oo = 1e14, N = 1e5 + 5;
int k, n, res, tst;
int lsum, rsum, pre[N];
vector<pair<int, int>> v;
priority_queue<int> pql;
priority_queue<int, vector<int>, greater<>> pqr;

bool comp(pair<int, int> x, pair<int, int> y){
  return x.first + x.second < y.first + y.second;
}

void add(int x){
  int mid = (pql.size() ? pql.top() : oo);
  if(x <= mid){
    pql.push(x);
    lsum += x;
  }else{
    pqr.push(x);
    rsum += x;
  }

  if(pqr.size() + 2 <= pql.size()){
    int t = pql.top(); pql.pop();
    pqr.push(t);
    lsum -= t;
    rsum += t;
  }else if(pql.size() < pqr.size()){
    int t = pqr.top(); pqr.pop();
    pql.push(t);
    lsum += t;
    rsum -= t;
  }
}

int32_t main()
{
  cin.tie(0)->sync_with_stdio(0); cout.tie(0);
  if(fopen("BRIDGES.inp", "r")){
    freopen("BRIDGES.inp", "r", stdin);
    freopen("BRIDGES.out", "w", stdout);
  }
  cin >> k >> n;
  v.push_back({0, 0});
  for(int i = 1; i <= n; i++){
    char p, q;
    int s, t;
    cin >> p >> s >> q >> t;
    if(p == q) tst += abs(s - t);
    else v.push_back({s, t});
  }
  sort(v.begin(), v.end(), comp);
  n = v.size()-1;
  tst += n;
  for(int i = 1; i <= n; i++){
    add(v[i].first);
    add(v[i].second);
    pre[i] = rsum - lsum;
  }
  res = pre[n];
  if(k == 2){
    while(pql.size()) pql.pop();
    while(pqr.size()) pqr.pop();
    lsum = rsum = 0;
    for(int i = n; i >= 1; i--){
      add(v[i].first);
      add(v[i].second);
      res = min(res, rsum - lsum + pre[i-1]);
    }
  }
  cout << tst + res;

  return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'int32_t main()':
bridge.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen("BRIDGES.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:44:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     freopen("BRIDGES.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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