fork(1) download 
  1. /*
  2.  * Comisia - Algoritmiada 2016 Runda 3 Seniori
  3.  * @Alex Tatomir
  4.  */
  5.  
  6. #include <iostream>
  7. #include <cstdio>
  8. #include <cstring>
  9. #include <vector>
  10. #include <algorithm>
  11. #include <cmath>
  12.  
  13. using namespace std;
  14.  
  15. #define mp make_pair
  16. #define pb push_back
  17. #define ll long long
  18.  
  19. #define maxN 200011
  20. #define maxLog 19
  21. #define inf 1000000000000000000LL
  22.  
  23. int n, i, j, l, r;
  24. ll sums[maxN];
  25. int rmq[maxLog][maxN];
  26. int help[maxN];
  27. ll ans = inf;
  28.  
  29. int query(int l, int r) {
  30.     int dim = (r - l + 1);
  31.     int id = help[dim];
  32.  
  33.     return max(rmq[id][l], rmq[id][r - (1 << id) + 1]);
  34. }
  35.  
  36. int main()
  37. {
  38.     freopen("comisia.in","r",stdin);
  39.     freopen("comisia.out","w",stdout);
  40.  
  41.     scanf("%d", &n);
  42.     for (i = 1; i <= n; i++) scanf("%d", &rmq[0][i]);
  43.     for (i = 1; i <= n; i++) scanf("%lld", &sums[i]), sums[i] += sums[i - 1];
  44.  
  45.  
  46.     help[1] = 0;
  47.     for (i = 1; i <= n; i++) {
  48.         help[i] = help[i - 1];
  49.         if (i >= (1 << help[i]) << 1) help[i]++;
  50.     }
  51.  
  52.     for (i = 1; i <= help[n]; i++) {
  53.         int big_dim = (1 << i);
  54.         int small_dim = big_dim >> 1;
  55.  
  56.         for (j = 1; j + big_dim - 1 <= n; j++)
  57.             rmq[i][j] = max(rmq[i - 1][j], rmq[i - 1][j + small_dim]);
  58.     }
  59.  
  60.     for (l = 1; l <= n; l++) {
  61.         r = l;
  62.  
  63.         while (r <= n) {
  64.             int need = query(l, r);
  65.             if (need <= r - l + 1) break;
  66.             r = l + need - 1;
  67.         }
  68.  
  69.         if (r <= n) ans = min(ans, sums[r] - sums[l - 1]);
  70.     }
  71.  
  72.     printf("%lld", ans);
  73.  
  74.     return 0;
  75. }
Success #stdin #stdout 0s 20648KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/O9R4iz
language:
C++14 (gcc 8.3)
created:
9 years 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!