Submission #67002424

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
inline long long read(){
	long long x=0; char ch;
	bool f=0;
	while(((ch=getchar())<'0'||ch>'9')&&ch!='-') ;
	if(ch=='-') f=1;
	else x=(x<<1)+(x<<3)+(ch^48);
	while((ch=getchar())>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48);
	return f?-x:x;
}
#define ll long long
const int N=2e5+5;
int n;
ll a[N],b[N],c[N],A[N],B[N],C[N],l[N],r[N];
int ok(ll md){
	if(md<=0) return 1;
	ll s1=0,re=0,s2=0;
	for(int i=1;i<=n;i++){
		a[i]=A[i];
		b[i]=B[i];
		c[i]=C[i];
		a[i]=min(a[i],b[i]);
		c[i]=min(c[i],b[i]);
		b[i]=min(b[i],a[i]+c[i]);
		s1=s1+a[i];
		s2=s2+min(c[i],b[i]-a[i]);
		re=re+a[i]-b[i]+c[i];
	}
	if(s1<md) return 0;
	if(s2+re<md) return 0;
	return s1+s2>=2*md;
}
void solve(){
	n=read();
	for(int i=1;i<=n;i++){
		a[i]=read(),b[i]=read(),c[i]=read();
		A[i]=a[i];
		B[i]=b[i];
		C[i]=c[i];
	}
	ll l=0,r=1e16;
	while(l<=r){
		ll md=(l+r)/2;
		if(ok(md)) l=md+1;
		else r=md-1;
	}
	printf("%lld\n",r);
}
int main(){
//	freopen("t1.in","r",stdin);
	int T=read();
	while(T--) solve();
	return 0;
}

Submission Info

Judge Result