Submission #1362356

#TimeUsernameProblemLanguageResultExecution timeMemory
1362356vyaductBikeparking (EGOI24_bikeparking)C++20
16 / 100
1095 ms9736 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int mxN = 300001;
ll x[mxN], y[mxN], X[mxN], Y[mxN];

/*
  Claim: The users giving a positive review 
  must form a subarray of y
  Proof: 
  Take users a < b < c
  Such that :
    user a took a seat in tier x < a
    user b took a seat in tier y > b
    user c took a seat in tier z < c
  We can get a similar or better score : 
    user a takes seat still in z
    user b takes seat in x
    user c takes seat in z
  This way, we have +1 from c (c > z)
  And we have +1 from b (x < a < b)
  And for c it doesnt matter since the situation is similar/better
*/

ll compute(ll l, ll n){
  for (ll i=0;i<n;i++) X[i] = x[i], Y[i] = y[i];
  ll ans = 0, i = l, j = 0;
  while(i<n){
    while(i<n && !Y[i]) i++;
    while(!X[j]) j++;
    if (i == n) break;
    ll s;
    if (i==j) s=0;
    else if (i<j) s=-1;
    else s=1;
    if (Y[i] <= X[j]){
      ans += Y[i] * s;
      X[j] -= Y[i];
      i++;
    } else {
      ans += X[j] * s;
      Y[i] -= X[j];
      j++;
    }
  }
  i = 0;
  while(i<l){
    while(i<l && !Y[i]) i++;
    while(!X[j]) j++;
    if (i == l) break;
    ll s;
    if (i==j) s=0;
    else if (i<j) s=-1;
    else s=1;
    if (Y[i] <= X[j]){
      ans += Y[i] * s;
      X[j] -= Y[i];
      i++;
    } else {
      ans += X[j] * s;
      Y[i] -= X[j];
      j++;
    }
  }
  return ans;
}

void solve(){
  ll n; cin>>n;
  for (ll i=0;i<n;i++) cin>>x[i];
  for (ll i=0;i<n;i++) cin>>y[i];
  ll ans = -1e18; 
  for (ll t=0;t<n;t++) ans = max(ans, compute(t, n));
  cout << ans << endl;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...