Facebook
From 5ちゃんねる, 3 Years ago, written in C++.
Embed
Download Paste or View Raw
Hits: 195
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     int n;
  6.     cin >> n;
  7.     vector<int> a(n);
  8.     for (int i = 0; i < n; i += 1) {
  9.         cin >> a[i];
  10.     }
  11.     vector<long long> sum(n + 1);
  12.     for (int i = 0; i < n; i += 1) {
  13.         sum[i + 1] += sum[i] + a[i];
  14.     }
  15.     auto diff = [&](int x) {
  16.         return sum[x] - (sum[n] - sum[x]);
  17.     };
  18.     int l = 0, r = n;
  19.     while (r - l > 1) {
  20.         int m = (l + r) / 2;
  21.         (diff(m) < 0 ? l : r) = m;
  22.     }
  23.     if (diff(l) < diff(r)) {
  24.         cout << l << " " << abs(diff(l)) << endl;
  25.     } else {
  26.         cout << r << " " << abs(diff(r)) << endl;
  27.     }
  28.     return 0;
  29. }
  30.