Submission #1164675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164675		Faisal_Saqib	Potatoes and fertilizers (LMIO19_bulves)	C++20	24 / 100	82 ms	22220 KiB

bulves

#include <bits/stdc++.h>

using namespace std;
#define ll long long
const ll N=5e5+10;
ll f[N],p[N];
void solve()
{
	ll n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		// ferti potato
		cin>>f[i]>>p[i];
		ll mn=min(f[i],p[i]);
		p[i]-=mn;
		f[i]-=mn;
	}
	// greedy
	queue<vector<int>> q;
	ll ans=0;
	for(int i=1;i<=n;i++)
	{
		while(q.size())
		{
			auto it=q.front();
			if(it[2]==0)break;
			q.pop();
			if(it[0]<=p[i])
			{
				ans+=1ll*(i-it[1])*it[0];
				p[i]-=it[0];
			}
			else
			{
				ans+=1ll*(i-it[1])*p[i];
				it[0]-=p[i];
				p[i]=0;
				q.push(it);
				break;
			}
		}
		if(p[i]>0)
			q.push({p[i],i,0});
		while(q.size())
		{
			auto it=q.front();
			if(it[2]==1)break;
			q.pop();
			if(it[0]<=f[i])
			{
				ans+=1ll*(i-it[1])*it[0];
				f[i]-=it[0];
				// opop
			}
			else
			{
				ans+=1ll*(i-it[1])*f[i];
				it[0]-=f[i];
				q.push(it);
				f[i]=0;
				break;
			}
		}
		if(f[i]>0)
			q.push({f[i],i,1});
	}
	cout<<ans<<endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	// cin>>t;
	while(t--)solve();
	return 0;
}

Compilation message (stderr)

bulves.cpp: In function 'void solve()':
bulves.cpp:44:36: warning: narrowing conversion of 'p[i]' from 'long long int' to 'int' [-Wnarrowing]
   44 |                         q.push({p[i],i,0});
      |                                 ~~~^
bulves.cpp:44:36: warning: narrowing conversion of 'p[i]' from 'long long int' to 'int' [-Wnarrowing]
bulves.cpp:66:36: warning: narrowing conversion of 'f[i]' from 'long long int' to 'int' [-Wnarrowing]
   66 |                         q.push({f[i],i,1});
      |                                 ~~~^
bulves.cpp:66:36: warning: narrowing conversion of 'f[i]' from 'long long int' to 'int' [-Wnarrowing]

• Subtask 1: 24 / 24
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 36