Submission #282673

#	Time	Username	Problem	Language	Result	Execution time	Memory
282673		nafis_shifat	Art Exhibition (JOI18_art)	C++14	50 / 100	1077 ms	20716 KiB

art

#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
using namespace std;
const int mxn=5e5+5;
const ll inf=1e18;

struct segtree {
	ll tree[4*mxn];

	void init() {
		for(int i=1;i<4*mxn;i++) tree[i]=-inf;
	}

	void update(int node,int b,int e,int p,ll v) {
		if(e<p || b>p)return;
		if(b==e) {
			tree[node]=v;
			return;
		}
		int mid=b+e>>1;
		int left=node<<1;
		int right=left|1;

		update(left,b,mid,p,v);
		update(right,mid+1,e,p,v);
		tree[node]=max(tree[left],tree[right]);
	}

} st;


int main() {
	int n;
	cin>>n;
	pii a[n];
	for(int i=0;i<n;i++) {
		cin>>a[i].first>>a[i].second;
	}

	sort(a,a+n);
	reverse(a,a+n);

	st.init();

	ll ps=0;

	for(int i=0;i<n;i++) {
		ps+=a[i].second;
		st.update(1,1,n,i+1,ps+a[i].first);
	}

	ps=0;
	ll ans=-inf;
	for(int i=0;i<n;i++) {
		ll v=st.tree[1];

		v-=ps+a[i].first;
		ans=max(ans,v);
		st.update(1,1,n,i+1,-inf);
		ps+=a[i].second;

	}

	cout<<ans<<endl;

	
}

Compilation message (stderr)

art.cpp: In member function 'void segtree::update(int, int, int, int, long long int)':
art.cpp:21:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |   int mid=b+e>>1;
      |           ~^~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 50