Submission #691263

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define all(c) ((c).begin()), ((c).end())
#define iter(c) __typeof((c).begin())
#define present(c, e) ((c).find((e)) != (c).end())
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define tr(c, i) for (iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb push_back
#define mp make_pair
 
typedef long long ll;
 
const ll INF = 1LL << 60;
 
typedef ll val_t;
 
struct node_t {
  val_t v;
  node_t *l, *r;
  node_t(val_t v) : v(v), l(NULL), r(NULL) {}
};
 
node_t *merge(node_t *x, node_t *y) {
  if (!x || !y) return x ? x : y;
  if (x->v > y->v) swap(x, y);
  x->r = merge(x->r, y);
  swap(x->l, x->r);
  return x;
}
 
node_t *add(node_t *x, val_t v) { return merge(x, new node_t(v)); }
node_t *pop(node_t *x) { return merge(x->l, x->r); }
 
ll fst(node_t *p) { return p ? p->v : INF; }
ll snd(node_t *p) { return p ? min(fst(p->l), fst(p->r)) : INF; }
 
 
 
 
typedef pair<ll, ll> pii;
 
node_t *hpq[100010];
ll rig[100010], lef[100010], cst[100010];
 
ll hu_tucker(ll N, ll *A) {
  priority_queue<pii, vector<pii>, greater<pii> > mpq;
 
  rep (i, N - 1) {
    hpq[i] = NULL;
    rig[i] = i + 1;
    lef[i] = i - 1;
    cst[i] = A[i] + A[i + 1];
    mpq.push(mp(cst[i], i));
  }
 
  ll ans = 0;
  rep (k, N - 1) {
    ll c, i;
    do {
      c = mpq.top().first;
      i = mpq.top().second;
      mpq.pop();
    } while (rig[i] == -1 || cst[i] != c);
 
    bool ml = false, mr = false;
    if (A[i] + fst(hpq[i]) == c) {
      hpq[i] = pop(hpq[i]);
      ml = true;
    }
    else if (A[i] + A[rig[i]] == c) {
      ml = mr = true;
    }
    else if (fst(hpq[i]) + snd(hpq[i]) == c) {
      hpq[i] = pop(pop(hpq[i]));
    }
    else {
      hpq[i] = pop(hpq[i]);
      mr = true;
    }
 
    ans += c;
    hpq[i] = add(hpq[i], c);
 
    if (ml) A[i] = INF;
    if (mr) A[rig[i]] = INF;
 
    if (ml && i > 0) {
      ll j = lef[i];
      hpq[j] = merge(hpq[j], hpq[i]);
      rig[j] = rig[i];
      rig[i] = -1;
      lef[rig[j]] = j;
      i = j;
    }
    if (mr && rig[i] + 1 < N) {
      ll j = rig[i];
      hpq[i] = merge(hpq[i], hpq[j]);
      rig[i] = rig[j];
      rig[j] = -1;
      lef[rig[i]] = i;
    }
 
    cst[i] = A[i] + A[rig[i]];
    cst[i] = min(cst[i], min(A[i], A[rig[i]]) + fst(hpq[i]));
    cst[i] = min(cst[i], fst(hpq[i]) + snd(hpq[i]));
    mpq.push(mp(cst[i], i));
  }
 
  return ans;
}
 
 
 
ll N, A[100010];
 
int main() {
  scanf("%lld", &N);
  rep (i, N) scanf("%lld", A + i);
  ll ans = hu_tucker(N, A);
  printf("%lld\n", ans);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:118:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &N);
                    ^
./Main.cpp:119:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   rep (i, N) scanf("%lld", A + i);
                                  ^

Judge Result