fork download 
  1. //#pragma GCC optimize("O3", "unroll-loops")
  2. //#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
  3.  
  4. #include <bits/stdc++.h>
  5. #define ldb long double
  6. //#define double ldb
  7. #define db double
  8. #define unomap unordered_map
  9. #define unoset unordered_set
  10. #define endl '\n'
  11. #define str string
  12. #define strstr stringstream
  13. #define sz(a) (int)a.size()
  14. #define ll long long
  15. #define int ll
  16. #define pii pair <int, int>
  17. #define pll pair <ll, ll>
  18. #define Unique(a) a.resize(unique(all(a)) - a.begin())
  19. #define ull unsigned ll
  20. #define fir first
  21. #define sec second
  22. #define idc cin.ignore()
  23. #define lb lower_bound
  24. #define ub upper_bound
  25. #define all(s) s.begin(), s.end()
  26. #define rev reverse
  27. #define gcd __gcd
  28. #define pushb push_back
  29. #define popb pop_back
  30. #define pushf push_front
  31. #define popf pop_front
  32. #define mul2x(a, x) a << x
  33. #define div2x(a, x) a >> x
  34. #define lcm(a, b) (a / __gcd(a, b) * b)
  35. #define log_base(x, base) log(x) / log(base)
  36. #define debug cerr << "No errors!"; exit(0);
  37. #define forw(i, a, b) for (int i = a; i <= b; ++i)
  38. #define forw2(i, a, b) for (ll i = a; i <= b; ++i)
  39. #define fors(i, a, b) for (int i = a; i >= b; --i)
  40. #define fors2(i, a, b) for (ll i = a; i >= b; --i)
  41. #define pqueue priority_queue
  42. #define sqrt sqrtl
  43. #define i128 __int128
  44. #define popcount __builtin_popcountll
  45. #define BIT(x, i) (((x) >> (i)) & 1)
  46. #define MASK(x) ((1LL) << (x))
  47. #define want_digit(x) cout << fixed << setprecision(x);
  48. #define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
  49. using namespace std;
  50. const int MOD = 1e9 + 7; // 998244353
  51. const int inf = 1e9;
  52. const ll INF = 1e18;
  53. const int N = 5e4;
  54.  
  55. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  56. ll random(const ll &L, const ll &R) {
  57.     return uniform_int_distribution<ll> (L, R) (rng);
  58. }
  59.  
  60. int n, p[N + 5];
  61. ll pre[N + 5], suf[N + 5], ans, sum[N + 5];
  62.  
  63. ll get(int l, int r) {
  64.     if (l > r) swap(l, r);
  65.     return sum[r] - sum[l - 1];
  66. }
  67.  
  68. ll square(ll x) {
  69.     return x * x;
  70. }
  71.  
  72. template <class X, class Y>
  73. bool minimize(X &x, const Y &y) {
  74.     return x > y ? x = y, true : false;
  75. }
  76.  
  77. void solve() {
  78.     cin >> n;
  79.     forw (i, 1, n) cin >> p[i], sum[i] = sum[i - 1] + p[i];
  80.  
  81.     forw (i, 2, n - 2)  {
  82.         pre[i] = INF;
  83.         ll goal = sum[i] / 2;
  84.         int pos = lb(sum + 1, sum + i, goal) - sum;
  85.         if (1 <= pos && pos < i)
  86.             pre[i] = square(sum[pos]) + square(get(pos + 1, i));
  87.  
  88.         --pos;
  89.         if (1 <= pos && pos < i)
  90.             minimize(pre[i], square(sum[pos]) + square(get(pos + 1, i)));
  91.     }
  92.     fors (i, n - 1, 3) {
  93.         suf[i] = INF;
  94.         ll goal = get(i, n) / 2;
  95.         int pos = lb(sum + i, sum + n, sum[i - 1] + goal) - sum;
  96.         if (i <= pos && pos < n)
  97.             suf[i] = square(get(i, pos)) + square(get(pos + 1, n));
  98.  
  99.         --pos;
  100.         if (i <= pos && pos < n)
  101.             minimize(suf[i], square(get(i, pos)) + square(get(pos + 1, n)));
  102.     }
  103.  
  104.     ans = INF;
  105.     forw (i, 2, n - 2)
  106.         ans = min(ans, pre[i] * suf[i + 1]);
  107.     cout << ans << endl;
  108. }
  109.  
  110. signed main() {
  111.     ios::sync_with_stdio(false), cin.tie(nullptr);
  112.     srand(time(NULL));
  113.     #define name "test"
  114.     if (fopen(name".INP", "r")) {
  115.         freopen(name".INP", "r", stdin);
  116.         freopen(name".OUT", "w", stdout);
  117.     }
  118.     bool testCase = false;
  119.     int numTest = 1;
  120. //    cin >> numTest;
  121.     forw (i, 1, numTest) {
  122.         if (testCase) cout << "Case " << i << ": ";
  123.         solve();
  124.     }
  125.     return 0;
  126. }
  127.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
6
1 1 2 1 1 2
stdout 
36
https://ideone.com/33k3rM
language:
C++14 (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!