C++14(g++5.4) 解法, 执行用时: 577ms, 内存消耗: 3296K, 提交时间: 2019-10-04 12:27:52

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100000+10;
int n;
ll l[N],cost[N];
char c;
struct node
{
	ll first,second;
}p;
bool operator<(node a,node b)
{
	if(a.second==b.second)return a.first<b.first;
	return a.second>b.second;
}
priority_queue<node>que;
int main()
{
	while(~scanf("%d",&n))
	{
		ll ans = 0;
		for(int i=1;i<=n;i++)
		{
			scanf("%lld %c %lld",&l[i],&c,&cost[i]);
			if(c=='(')
			{
				ans+=l[i]*cost[i];
				cost[i]=-cost[i];
			}
		}
		while(!que.empty())
		{
			que.pop();
		}
		ll k = 0;
		ll tot = 0;	
		ll ret = 0;
		for(int i=1;i<=n;i++)
		{
			p.first = l[i];
			p.second = cost[i];
			que.push(p);
			tot += l[i];
			ret = (tot + 1) /2 - k;
			k = ( tot + 1) /2 ;
			while(ret > 0 && !que.empty())
			{
				p=que.top();
				que.pop();
				
				ll ch_right_num= min(p.first,ret);
				ret -= ch_right_num;
				
				ans += ch_right_num * p.second;
				p.first  -= ch_right_num;
				
				if(p.first > 0 )
					que.push(p);
			}
		}
		
		printf("%lld\n",ans);
	}
	return 0; 
}

C++11(clang++ 3.9) 解法, 执行用时: 622ms, 内存消耗: 18060K, 提交时间: 2019-10-04 20:39:37

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

using namespace std;
const int mod=1e9+7;
int n;
struct node
{
	int l,d;
	bool operator<(const node v)const
	{
		if(d==v.d)
			return l>v.l;
		return d>v.d;
	}
};

int main()
{
	#ifndef ONLINE_JUDGE
		int startTime=clock();
	#endif	
	while(scanf("%d",&n)!=EOF)
	{
		ll ans=0,now=0;
		int l,d;
		char ch;
		priority_queue<node> pq;
		for(int i=0;i<n;i++)
		{
			scanf("%d %c %d",&l,&ch,&d);
			if(ch=='(')
			{
				ans+=1LL*l*d;
				d*=-1;
			}
			pq.push({l,d});
			int res=(now+l+1)/2-(now+1)/2;
			node t;
			while(!pq.empty())
			{
				if(!res) break;
				t=pq.top(),pq.pop();
				int num=min(t.l,res);
				ans+=1LL*t.d*num;
				res-=num;
				if(num<t.l)
					pq.push({t.l-num,t.d});
			}
			now+=l;
		}
		printf("%lld\n",ans);
	}
	#ifndef ONLINE_JUDGE
		printf("Time = %dms\n",(int)clock()-startTime);
	#endif
	return 0;
}