Submission #22667

#	Time	Username	Problem	Language	Result	Execution time	Memory
22667		past future present (#40)	Unifying Values (KRIII5_UV)	C++14	7 / 7	356 ms	2452 KiB

UV

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
int n;
ll a[10101];
ll sum[101010];
ll ans;
ll p[10101];

ll pow2(int x){
    ll t = 2;
    ll r = 1;
    while(x){
        if(x&1){
            r = (r*t)%mod;
        }
        t = (t*t)%mod;
        x>>=1;
    }
    return r;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        sum[i] = sum[i-1] + a[i];
    }

    for(int i=1;i<n;i++){
        ll x = sum[i];
        if(x==0){
            int c = 0;
            if(sum[n]!=0)continue;
            for(int j=i+1;j<n;j++){
                if(sum[j]==0)c++;
            }
            ans+=pow2(c);
            ans%=mod;
            continue;
        }
        if(sum[n]%x != 0)continue;
        ll mx = sum[n]/x;
        if(mx <=1)continue;
        if(mx > n)continue;
        vector<ll> v;
        v.push_back(1);
        for(int j=i+1;j<n;j++){
            if(sum[j]%x == 0){
                ll t = sum[j]/x;
                if(t > 1 && t < mx)v.push_back(t);
            }
        }
        v.push_back(mx);
        fill(p,p+n+1,0);
        p[0]=1;
        for(auto t : v){
            p[t]+=p[t-1];
            p[t]%=mod;
        }
        ans+=p[v.back()];
        ans%=mod;
    }
    printf("%lld\n",ans);
}

Compilation message (stderr)

UV.cpp: In function 'int main()':
UV.cpp:26:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
UV.cpp:28:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&a[i]);
                            ^

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5