Submission #1151585

#TimeUsernameProblemLanguageResultExecution timeMemory
1151585KaleemRazaSyedBikeparking (EGOI24_bikeparking)C++20
25 / 100
153 ms16844 KiB
#include<bits/stdc++.h>

using namespace std;

int main()
{
  int n;
  cin >> n;
  
  int x[n], y[n];
  for(int i = 0; i < n; i ++)
    cin >> x[i];  
  for(int i = 0; i < n; i ++)
    cin >> y[i];
  
  int sm = 0;
  for(int i = 0; i < n; i ++)
    sm += y[i];
	  
  for(int i = 0; i < n; i ++)
    {
      x[i] = min(sm, x[i]);
      sm -= x[i];
    }
	  
  int ans = 0;
  set<int> st;
  for(int i = 0; i < n; i ++) {
    if(x[i] > 0)
      st.insert(i);
  }

  for(int i = n - 1; i >= 0; i--)
    {
      while(y[i] > 0)
	{
	  auto it = st.lower_bound(i);
	  if(it != st.begin())
	    {
	      it--;
	      int j = *it;
	      int mi = min(y[i], x[j]);
	      y[i] -= mi;
	      x[j] -= mi;
	      ans += mi;
	      if(x[j] == 0) st.erase(j); 
	    }
	  else
	    {
	      it--;
	      int j = *it;
	      int mi = min(y[i], x[j]);
	      y[i] -= mi;
	      x[j] -= mi;
	      if(j > i)
		ans -= mi;
	      if(x[j] == 0) st.erase(j); 
	    }
	}
    }
  cout << ans << endl;
  return 0;
}
#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...