Submission #1151592

#TimeUsernameProblemLanguageResultExecution timeMemory
1151592Faisal_SaqibBikeparking (EGOI24_bikeparking)C++20
100 / 100
81 ms3912 KiB
#include <bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int x[N],y[N],par[N];
int get(int x)
{
	if(par[x]==x)
		return x;
	return par[x]=get(par[x]);
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		par[i]=i;
	}
	for(int i=1;i<=n;i++)
	{
		cin>>x[i];
	}
	for(int i=1;i<=n;i++)
	{
		cin>>y[i];
	}
	// {

	int p=0;
	int cur=0,tp=0,zero=0;
	// for(int i=n;i>=1;i--)
	for(int i=n;i>=0;i--)
	{
		// cur is sum of y over [i+1,n]
		int mn=min(cur,x[i]);
		cur-=mn;
		x[i]-=mn; 
		p+=mn; // profit
		// zero not now later
		// we need maximum zeros
		zero=min(zero,cur);
		zero+=min(x[i],y[i]);


		cur+=y[i];
		tp+=x[i];
	}
	// cout<<p<<endl;
	// cout<<' '<<tp<<' '<<cur<<endl;
	p-=(min(tp,cur)-zero);
	cout<<p<<endl;
	// }
	// p+=max(0,tp-cur);
	// for(int i=1;i<=n;i++)
		// p+=x[i];
}
#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...