fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false) ; cin.tie(NULL)
  4.  
  5. const long long INF = 1e16;
  6. const int N = 5e5 + 7;
  7. int n;
  8. long long a[N] , b[N] , pre[N] , L[N] , R[N] , _max[N];
  9.  
  10. void build_L(){
  11.     _max[n + 1] = -INF;
  12.     for (int i = n ; i >= 1 ; --i){
  13.         _max[i] = max(_max[i + 1] , a[i] - pre[i - 1]);
  14.     }
  15.     long long sum = 0;
  16.     for (int i = 1 ; i <= n ; ++i){
  17.         L[i] = sum + _max[i];
  18.         sum += b[i];
  19.     }
  20. }
  21.  
  22. void build_R(){
  23.     memset(_max , 0 , sizeof _max);
  24.     for (int i = 1 ; i <= n ; ++i){
  25.         _max[i] = max(_max[i - 1] , a[i] - pre[i - 1]);
  26.     }
  27.  
  28.     long long sum = pre[n];
  29.     for (int i = 1 ; i <= n ; ++i){
  30.         sum -= b[i];
  31.         R[i] = _max[i] - sum;
  32.     }
  33. }
  34.  
  35. void inp(){
  36.     cin >> n;
  37.     for (int i = 1 ; i <= n ; ++i){
  38.         cin >> a[i];
  39.     }
  40.     for (int i = 1 ; i <= n ; ++i){
  41.         cin >> b[i];
  42.         pre[i] = pre[i - 1] + b[i];
  43.     }
  44.     build_L();
  45.     build_R();
  46. }
  47.  
  48. void solve(){
  49.     long long res = INF;
  50.     for (int i = 1 ; i <= n ; ++i){
  51.         res = min(res , max(L[i] , R[i - 1]));
  52.     }
  53.  
  54.     cout << res;
  55. }
  56.  
  57. int main(){
  58.     faster;
  59.     inp();
  60.     solve();
  61.     return 0;
  62. }
Success #stdin #stdout 0.01s 9444KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10000000000000000
https://ideone.com/c9MAKb
language:
C++14 (gcc 8.3)
created:
9 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!