Submission #1151828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151828		KaleemRazaSyed	Bikeparking (EGOI24_bikeparking)	C++20	25 / 100	169 ms	19560 KiB

Main

#include<bits/stdc++.h>

using namespace std;

const int N = 3e5 + 10;
int n;
vector<int> x, y;

int solve2(vector<int> x, vector<int> y)
{
 int ans = 0;
  set<int> st;
  for(int i = 0; i < n; i ++)
    {
      while(y[i] > 0 && st.size())
	{
	  int j = *st.begin();
	  int mi = min(x[j], y[i]);
	  x[j] -= mi;
	  y[i] -= mi;
	  ans += mi;
	  if(x[j] == 0) st.erase(j);
	}
      
      if(x[i] > 0) st.insert(i);
    }

  for(int i = n - 1; i >= 0; i--)
    {
      while(y[i] > 0)
	{
	  int j = *st.begin();
	  int mi = min(x[j], y[i]);
	  x[j] -= mi;
	  y[i] -= mi;
	  if(j > i) ans -= mi;
	  if(x[j] == 0) st.erase(j);
	}
    }
    return ans;
}

int solve1(vector<int> x, vector<int> y)
{
  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;
	      if(j < i)
		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); 
	    }
	}
    }
  return ans;
}

int main()
{
 
  cin >> n;
  x.resize(n), y.resize(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 s1 = max(solve2(x, y), solve1(x, y));
  
  int ans = 0;
  int s = 0, e = n - 1;
  for(int i = 0; i < n; i++)
    {
      while(y[i]  > 0)
	{
	  if(i > s)
	    {
	      int mi = min(y[i], x[s]);
	      x[s] -= mi;
	      y[i] -= mi;
	      if(i > s) ans += mi;
	      if(!x[s]) s++;
	    }
	  else
	    {
	      int mi = min(y[i], x[e]);
	      x[e] -= mi;
	      y[i] -= mi;
	      if(e > i) ans -= mi;
	      if(!x[e]) e--;
	    }
	}
    }
  cout << max(ans, s1) << endl;
 
  return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 9 / 9
• Subtask 3: 0 / 19
• Subtask 4: 0 / 24
• Subtask 5: 0 / 32