제출 #1157629

#제출 시각아이디문제언어결과실행 시간메모리
1157629dashkaBikeparking (EGOI24_bikeparking)C++20
100 / 100
145 ms15448 KiB
#include<bits/stdc++.h>

using namespace std;

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


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

  for(int i = n - 1; i >= 0; i--)
    {
      while(x[i] > 0)
	{
	  int j = *st.begin();
	  int mi = min(x[i], y[j]);
	  x[i] -= mi;
	  y[j] -= mi;
	  if(i > j) ans -= mi;
	  if(y[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...