Submission #81562

#	Time	Username	Problem	Language	Result	Execution time	Memory
81562		farukkastamonuda	Art Exhibition (JOI18_art)	C++14	100 / 100	456 ms	243044 KiB

art

#include <bits/stdc++.h>
#define fi first
#define se second
#define lo long long 
#define inf 1000000009
#define md 1000000007
#define li 500005
#define mp make_pair
#define pb push_back
using namespace std;
int n,flag;
lo int val,mx;
pair<lo int,lo int> p[li];
vector< pair<lo int,lo int> > v;
priority_queue< pair<lo int,lo int> > q;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld %lld",&p[i].fi,&p[i].se);
	}
	sort(p+1,p+n+1);
	for(int i=1;i<=n;i++){
		val+=p[i].se;
		lo int val2=p[i].se;
		while(i<n && p[i+1].fi==p[i].fi){
			val+=p[i+1].se;
			val2+=p[i+1].se;
			i++;
		}
		v.push_back(mp(p[i].fi,val));
		mx=max(mx,val-(p[i].fi-p[1].fi));
		q.push(mp(val-(p[i].fi-p[1].fi),p[i].fi));
	}
	for(int i=0;i<(int)v.size();i++){
		if(i==0) continue;
		lo int go=v[i].fi;
		//int deg=v[i].se;
		lo int extra=-v[i-1].se+go-v[0].fi;
		while(!q.empty()){
			pair<lo int,lo int> temp=q.top();
			q.pop();
			if(temp.se<go) continue;
			mx=max(mx,temp.fi+extra);
			q.push(temp);
			//q.push(mp(temp.fi+extra,go));
			break;
		}
	}
	printf("%lld\n",mx);
	return 0;
}

Compilation message (stderr)

art.cpp: In function 'int main()':
art.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
art.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&p[i].fi,&p[i].se);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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