【題解】Google Kick Start 2020 Round C – p3. Perfect Subarray

#include <iostream>
#include <cmath>
using namespace std;

const int m = 10000000;
int t, n, a[100005], b[20000005];
long long ans;

int main() {
    cin >> t;
    for (int Case = 1; Case <= t; Case++){
        cin >> n;
        int mn = 0;
        ans = 0;
        b[m] = 1;
        int *dp = b+m;
        for (int i = 1; i <= n; i++){
            cin >> a[i];
            dp += a[i];
            a[i] += a[i-1];
            for (int j = sqrt(a[i]-mn); j >= 0; j--){
                ans += *(dp-j*j);
            }
            (*dp)++;
            mn = min(mn, a[i]);
        }
        for (int i = 0; i <= n; i++){
            b[a[i]+m]--;
        }
        cout << "Case #" << Case << ": " << ans << "\n";
    }
}