Submission #1164844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164844		KaleemRazaSyed	Potatoes and fertilizers (LMIO19_bulves)	C++20	24 / 100	401 ms	66732 KiB

bulves

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int n;
  cin >> n;

  int a[n], b[n];
  for(int i = 0; i < n; i ++)
    cin >> a[i] >> b[i];

  set<int> st;
  for(int i = 0; i < n; i ++)
    if(a[i])
      st.insert(i);

  set<pair<int,pair<int,int> > > sol;
  for(int i = 0; i < n; i ++)
    {
      while(b[i])
	{
	  int x = min(b[i], a[*st.begin()]);
	  a[*st.begin()] -= x;
	  b[i] -= x;
	  // cerr << x << ' ' << abs(i - *st.begin()) << endl;
	  sol.insert({i, {-abs(i - *st.begin()), x}});

	  if(!a[*st.begin()])
	    st.erase(st.begin());
	}
    }
  long long ans = 0;
  /* for(int i = n - 1; i >= 0; i--)
    {
      while(sol.size() && sol.rbegin()->first > i)
	{
	  ans += -1ll * (sol.rbegin()->second.first) * (sol.rbegin()->second.second);
	  sol.erase(--sol.end());
	}

      while(a[i] > 0 && sol.size())
	{
	  if(-sol.rbegin()->second.first < abs(i - sol.rbegin()->first))
	    {
	      int cnt = sol.rbegin()->second.second, idx = sol.rbegin()->first;
	      int x = min(cnt, a[i]), d = sol.rbegin()->second.first;
	      cerr << x << endl;
	      cerr << d << ' ' << abs(i - idx) << endl;
	      sol.erase(--sol.end());
	      cnt -= x;
	      a[i] -= x;
	      if(cnt > 0)
		sol.insert({idx,{d, cnt}});
	      sol.insert({idx,{idx - i, x}});
	      
	    }
	  else
	    break;
	}
	}*/
  for(auto x : sol)
    ans += -1ll * x.second.first * x.second.second;
  cout << ans << endl;
  return 0;
}

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