Submission #691178

---

Source Code Expand

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii;
typedef long long ll; typedef vector<long long> vl; typedef pair<long long, long long> pll; typedef vector<pair<long long, long long> > vpll;
typedef vector<string> vs; typedef long double ld;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

namespace leftist_heap {
typedef long long Val;
typedef less<Val> Cmp;
Cmp cmp = Cmp();

struct Node {
	Val val;
	Node *left, *right;
	int height;
	Node() {}
	Node(const Val &val_) : val(val_), left(NULL), right(NULL), height(0) {}
};

Node *meld(Node *x, Node *y) {
	if(!x || !y) return x ? x : y;
	if(cmp(y->val, x->val)) swap(x, y);
	x->right = meld(x->right, y);
	if(!x->left || x->left->height < x->right->height)
		swap(x->left, x->right);
	x->height = (x->right ? x->right->height : 0) + 1;
	return x;
}

Node *pop(Node *x) {
	return meld(x->left, x->right);
}
}

//参照: <http://www.cs.rit.edu/~std3246/thesis/>
//参考: iwiwi氏のコード
namespace hu_tacker {
namespace heap = leftist_heap;
typedef heap::Val Val;
const Val InfVal = numeric_limits<Val>::max() / 2;

Val fst(const heap::Node *t) {
	if(!t) return InfVal;
	return t->val;
}
Val snd(const heap::Node *t) {
	if(!t || (!t->left && !t->right)) return InfVal;
	if(!t->left) return t->right->val;
	if(!t->right) return t->left->val;
	return min(t->left->val, t->right->val);
}

Val optimalBinarySearchTree(vector<Val> w) {
	typedef pair<Val, int> P;
	int n = w.size();

	vector<heap::Node> nodes(n - 1);
	vector<heap::Node*> hpq(n, NULL);
	vector<int> left(n), right(n);	//番兵がある
	vector<Val> cost(n - 1);
	priority_queue<P, vector<P>, greater<P> > mpq;

	rep(i, n - 1) {
		left[i] = i - 1;
		right[i] = i + 1;
		mpq.push(make_pair(cost[i] = w[i] + w[i + 1], i));
	}
	Val ans = 0;
	rep(k, n - 1) {
		Val c; int i;
		do {
			c = mpq.top().first; i = mpq.top().second;
			mpq.pop();
		} while(right[i] == -1 || cost[i] != c);	//ヒープでのdeleteに対応

		bool ml = false, mr = false;
		if(w[i] + fst(hpq[i]) == c) {
			hpq[i] = heap::pop(hpq[i]);
			ml = true;
		} else if(w[i] + w[right[i]] == c) {
			ml = mr = true;
		} else if(fst(hpq[i]) + snd(hpq[i]) == c) {
			hpq[i] = heap::pop(heap::pop(hpq[i]));
		} else {
			hpq[i] = heap::pop(hpq[i]);
			mr = true;
		}

		ans += c;
		nodes[k] = heap::Node(c);
		hpq[i] = heap::meld(hpq[i], &nodes[k]);

		if(ml) w[i] = InfVal;
		if(mr) w[right[i]] = InfVal;

		if(ml && i > 0) {
			int j = left[i];
			hpq[j] = heap::meld(hpq[j], hpq[i]);
			left[right[j] = right[i]] = j; right[i] = -1;
			i = j;
		}
		if(mr && right[i] + 1 < n) {
			int j = right[i];
			hpq[i] = heap::meld(hpq[i], hpq[j]);
			left[right[i] = right[j]] = i; right[j] = -1;
		}

		Val v = w[i] + w[right[i]];
		v = min(v, min(w[i], w[right[i]]) + fst(hpq[i]));
		v = min(v, fst(hpq[i]) + snd(hpq[i]));
		mpq.push(make_pair(cost[i] = v, i));
	}

	return ans;
}
}

int main() {
	int N;
	while(~scanf("%d", &N)) {
		vector<long long> w(N);
		rep(i, N) scanf("%lld", &w[i]);
		long long ans = hu_tacker::optimalBinarySearchTree(w);
		printf("%lld\n", ans);
	}
	return 0;
}

Submission Info

Compile Error

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

Judge Result