fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define FAST std::ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(0);
  4. typedef long long ll;
  5. const int N = 1e8 + 1;
  6. void solve() {
  7.     int n; cin >> n;
  8.     vector<ll> a(n);
  9.     ll sum = 0;
  10.     for (int i = 0; i < n; i++)
  11.     {
  12.         cin >> a[i];
  13.         sum += a[i];
  14.     }
  15.     int s = a[0];
  16.     vector<bool> isHere(N, false);
  17.     isHere[s] = true;
  18.     for (int i = 1; i < n; i++) {
  19.         s += a[i];
  20.         isHere[s] = true;
  21.     }
  22.     // a.push_back(a[0]);
  23.     // a.push_back(a[1]);
  24.     if (sum % 3 != 0) return void(cout << 0);
  25.     int target = sum / 3, temp = 0, ans = 0;
  26.     sum = 0;
  27.     int r = 0;
  28.     for (int i = 0; i < n - 1; i++)
  29.     {
  30.         while (r < n)
  31.         {
  32.             if (temp + a[r] < target) { temp += a[r]; sum += a[r]; r++; }
  33.             else if (temp + a[r] == target) { temp += a[r]; sum += a[r]; if (isHere[sum + 8 - 1]) ans++; r++;}
  34.             else break;
  35.         }
  36.         // cout << temp << '\n';
  37.         temp -= a[i];
  38.     }
  39.     cout << ans / 2;
  40.  
  41. }
  42.  
  43. int main () {
  44.     FAST
  45.     //freopen("input.txt", "r", stdin);
  46.     //freopen("output.txt", "w", stdout);
  47.     int n; cin >> n;
  48.     int arr[n];
  49.     int sum = 0;
  50.     for(int i = 0; i < n; i++){
  51.         cin >> arr[i];
  52.         sum += arr[i];
  53.     }
  54.     if(sum % 3 != 0) {
  55.         cout << 0;
  56.         return 0;
  57.     }
  58.     int target = sum / 3;
  59.     int idx = 0;
  60.     for(int i = 0; i < n; i++) {
  61.         idx += arr[i];
  62.         if(idx >= target/**/) {
  63.             idx = i;
  64.             break;
  65.         }
  66.     }
  67.     int i = 0, j = 0, ans = 0;
  68.     sum = 0;
  69.     while(j < n) {
  70.         sum += arr[j];
  71.         if(sum == target) {
  72.             ans++;
  73.             sum -= arr[i];
  74.             i++;j++;
  75.         } else if(sum < target) {
  76.             j++;
  77.         } else {
  78.             sum -= arr[i];
  79.             i++; j++;
  80.         }
  81.     }
  82.     j = 0;
  83.     sum -= arr[i];
  84.     i++;
  85.     while(j < idx) {
  86.         sum += arr[j];
  87.         if(sum == target) {
  88.             ans++;
  89.             sum -= arr[i];
  90.             i++;j++;
  91.         } else if(sum < target) {
  92.             j++;
  93.         } else {
  94.             sum -= arr[i];
  95.             i++; j++;
  96.         }
  97.     }
  98.     cout << ans / 3 << endl;
  99. }
Success #stdin #stdout 0.01s 5532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/yQ4Xv8
language:
C++14 (gcc 8.3)
created:
1 year 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!