제출 #1345616

#제출 시각아이디문제언어결과실행 시간메모리
1345616Faisal_SaqibPotatoes and fertilizers (LMIO19_bulves)C++20
34 / 100
50 ms15860 KiB
#include <iostream>
using namespace std;
const int N=1e6+10;
typedef long long ll;
ll p1[N],p2[N],b1[N];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	int a[n],b[n];
	for(int i=0;i<n;i++)
	{
		cin>>a[i]>>b[i];
	}
	long long bal=0,fnl=0;
	for(int i=0;i<n;i++)
	{
		bal+=b[i];
		bal-=a[i];
		b1[i]=bal;
		fnl+=max(0ll,-bal);
		// cout<<bal<<' ';
	}
	// cout<<endl;
	for(int i=n-1;i>=0;i--)
		p1[i]=p1[i+1]+(b1[i]<0);
	// suf
	bal=0;
	for(int i=n-1;i>=0;i--)
	{
		bal+=b[i];
		bal-=a[i];
		b1[i]=bal;
		fnl+=max(0ll,-bal);
		// cout<<bal<<' ';
	}
	// cout<<endl;	
	for(int i=0;i<n;i++)
	{
		p2[i]=0;
		if(i)p2[i]=p2[i-1];
		p2[i]+=(b1[i]<0);
		// cout<<b1[i]<<' ';
	}
	// cout<<endl;
	ll og=0;
	for(int i=0;i<n;i++)og=max(og,p2[i]+p1[i]);
	// cout<<fnl<<endl;
	// cout<<og<<endl;
	cout<<fnl-og*(bal!=0)<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...