oj.uz

Submission #66740

# Submission time Handle Problem Language Result Execution time Memory
66740 2018-08-12T08:35:17 Z quoriess Art Exhibition (JOI18_art) C++14
0 / 100
 3 ms 360 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];
		ans=max(snc,ans);
	}


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


/*#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pii;
vector<pii> arts;
int main(){
	int n;
	cin>>n;
	vector<lli> prefVal(n);
	for (int i = 0; i < n; i++)
	{
		pii a;
		cin>>a.first>>a.second;
		arts.push_back(a);
	}
	sort(arts.begin(),arts.end());
	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;
	}
	vector<int> opt(n,0),optDeger(n,0);
	lli ans=0;
	for (int i = 0; i < n; i++)
	{
		for (int j = i; j < n; j++)
		{
			lli snc=prefVal[j]-(i==0?0:prefVal[i-1])+arts[i].first-arts[j].first;
			if(snc>optDeger[j]){
				optDeger[j]=snc;
				opt[j]=i;
			}
			if(snc>ans)
			{
				ans=snc;
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		cout << "opt: "<<i<<":"<< opt[i]<<"\n";
	}

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

Subtask #1
0 / 10.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 50.0

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