Google Kickstart Round C problem C


Getting Runtime Error
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define lld long long int 

//-4%3=-1
int main() {
	// your code goes here
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lld t;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        int n,sum=0;;
        cin>>n;
        int arr[n];
        for(int j=0;j<n;j++)
        {
            cin>>arr[j];
            sum+=arr[j];
        }
        vector <int> mp(2*sum+1);
        //unordered_map <int,int> mp;
        mp[sum]++;
        lld res=0,pref=0;
        for(int j=0;j<n;j++)
        {
            pref+=arr[j];
            for(int k=0;k*k<=sum+pref;k++)
            {
                lld need=pref+sum-k*k;
                res+=mp[need];
            }
            mp[sum+pref]++;
            //cout<<"A"<<pref<<" "<<mp[pref]<<"\n";
        }
        cout<<"Case #"<<i<<": "<<res<<"\n";
    }
}

When I comment the vector initialization part and uncomment map part, then it shows TLE.
Can someone tell my mistake?
@ssjgz @galencolin @everule1

sum could be negative, and STL has no idea how to create a vector with negative size

1 Like

Oh I missed it. My mistake.
Thanks a lot.