fork download
copy 
  1. // ~~ icebear ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define int long long
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<ii, int> iii;
  8.  
  9. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  10. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  11. #define rep(i, n) for(int i=0; i<(n); ++i)
  12. #define red(i, n) for(int i=(n)-1; i>=0; --i)
  13. #define mp make_pair
  14. #define pb push_back
  15. #define fi first
  16. #define se second
  17. #define all(x) x.begin(), x.end()
  18. #define task "icebearat"
  19.  
  20. const int MOD = 1e9 + 7;
  21. const int inf = 1e9 + 27092008;
  22. const ll LLinf = 1e18 + 27092008;
  23. const int N = 2e5 + 5;
  24. int n, a[N], p[N], st[N << 2], lazy[N << 2];
  25. int sum_pref = 0, sum_suff = 0, ans = LLinf;
  26.  
  27. void pushDown(int id) {
  28.     int &t = lazy[id];
  29.     if (t) {
  30.         st[id << 1] += t;
  31.         st[id << 1 | 1] += t;
  32.         lazy[id << 1] += t;
  33.         lazy[id << 1 | 1] += t;
  34.         t = 0;
  35.     }
  36. }
  37.  
  38. void update(int id, int l, int r, int u, int v, int k) {
  39.     if (l > v || r < u) return;
  40.     if (u <= l && r <= v) {
  41.         st[id] += k;
  42.         lazy[id] += k;
  43.         return;
  44.     }
  45.     pushDown(id);
  46.     int mid = (l + r) >> 1;
  47.     update(id << 1, l, mid, u, v, k);
  48.     update(id << 1 | 1, mid + 1, r, u, v, k);
  49.     st[id] = min(st[id << 1], st[id << 1 | 1]);
  50. }
  51.  
  52. void solve() {
  53.     cin >> n;
  54.     FOR(i, 1, n) cin >> p[i];
  55.     FOR(i, 1, n) {
  56.         cin >> a[i];
  57.         sum_suff += a[i];
  58.         update(1, 1, n, p[i] + 1, n, +a[i]);
  59.     }
  60.     FOR(i, 1, n - 1) {
  61.         sum_pref += a[i];
  62.         sum_suff -= a[i];
  63.         update(1, 1, n, p[i] + 1, n, -a[i]);
  64.         update(1, 1, n, 1, p[i] - 1, a[i]);
  65.         ans = min({ans, sum_pref, sum_suff, st[1]});
  66.     }
  67.  
  68.     cout << ans;
  69. }
  70.  
  71. signed main() {
  72.     ios_base::sync_with_stdio(0);
  73.     cin.tie(0); cout.tie(0);
  74.     if (fopen(task".inp", "r")){
  75.         freopen(task".inp", "r", stdin);
  76.         freopen(task".out", "w", stdout);
  77.     }
  78.     int tc = 1;
  79. //     cin >> tc;
  80.     while(tc--) solve();
  81.     return 0;
  82. }
  83.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000027091968
https://ideone.com/NRLeR3
language:
C++ (gcc 8.3)
created:
1 day 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!