oj.uz

Submission #66747

# Submission time Handle Problem Language Result Execution time Memory
66747 2018-08-12T08:42:30 Z quoriess Art Exhibition (JOI18_art) C++14
0 / 100
 3 ms 488 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pii;
vector<pii> arts;
const int MAXN=5*1e5+5;
#define  boy first;
#define  value second;
int main(){
	int n;
	cin>>n;
	vector<lli> prefVal(n);

	lli ans=-10;
	for (int i = 0; i < n; i++)
	{
		pii a;
		cin>>a.first>>a.second;
		ans=max(ans,a.second);
		arts.push_back(a);
	}
	sort(arts.begin(),arts.end());
	vector<lli> minim(n,0),minimaxi(n,0);
	minimaxi[0]=minim[0]=arts[0].first;
	for (int i = 0; i < n; i++)
	{
		pii a=arts[i];
		if(i==0)prefVal[0]=a.second;
		else prefVal[i]=prefVal[i-1]+a.second;
		if(i!=0){
			minim[i]=arts[i].first-arts[i-1].first-arts[i-1].second;
			minimaxi[i]=max(minimaxi[i-1],minim[i]);
		}
	}
	for (int i = 1; i < n; i++)
	{
		lli snc=prefVal[i]-arts[i].first+minimaxi[i-1];
		ans=max(snc,ans);
	}


	cout <<ans<<"\n";
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Incorrect 2 ms 488 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Incorrect 2 ms 488 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Incorrect 2 ms 488 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Incorrect 2 ms 488 KB Output isn't correct
3 Halted 0 ms 0 KB -