Submission #197847

#	Time	Username	Problem	Language	Result	Execution time	Memory
197847		quocnguyen1012	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	419 ms	14668 KiB

bridge

#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 5;

pair<int, int> a[maxn];
int n, k, N;

vector<ll> calc(void)
{
  vector<ll> ret(n + 5);
  multiset<int> l, r;
  ll suml = 0, sumr = 0;
  for (int i = 1; i <= n; ++i){
    suml += a[i].fi;
    sumr += a[i].se;
    l.insert(a[i].fi); r.insert(a[i].se);
    while (*l.rbegin() > *r.begin()){
      sumr += *l.rbegin() - *r.begin();
      suml += *r.begin() - *l.rbegin();
      l.insert(*r.begin());
      r.insert(*l.rbegin());
      l.erase(l.find(*l.rbegin()));
      r.erase(r.begin());
    }
    ret[i] = sumr - suml;
  }
  return ret;
}

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> k >> N;
  ll sum = 0;
  while (N--){
    int l, r;
    char t1, t2;
    cin >> t1 >> l >> t2 >> r;
    if (t1 == t2) sum += abs(l - r);
    else a[++n] = mp(l, r);
  }
  sort(a + 1, a + 1 + n, [&](pair<int, int> x, pair<int, int> y){
    return x.fi + x.se < y.fi + y.se;
  });
  vector<ll> pref = calc();
  reverse(a + 1, a + 1 + n);
  vector<ll> suff = calc();
  if (k == 1){
    cout << sum + n + pref[n];
  }
  else{
    ll res = 1e17;
    //cerr << sum << ' ' << n << '\n';
    for (int i = 0; i <= n; ++i){
      res = min(res, pref[i] + suff[n - i]);
    }
    cout << sum + n + res << '\n';
  }
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
bridge.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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