oj.uz

Submission #22609

# Submission time Handle Problem Language Result Execution time Memory
22609 2017-04-30T05:55:56 Z past future present(#977, kazel, pjh0123, nemo) Unifying Values (KRIII5_UV) C++14
0 / 7
 39 ms 2452 KB 
#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;j<=n;j++){
                if(sum[j]==0)c++;
            }
            ans+=pow2(c-2);
            ans%=mod;
            continue;
        }
        if(sum[n]/x*x != sum[n])continue;
        ll mx = sum[n]/x;
        if(mx == 1)continue;
        vector<ll> v;
        fill(p,p+n+1,0);
        v.push_back(1);
        for(int j=i+1;j<=n;j++){
            if(sum[j]/x*x == sum[j]){
                ll t = sum[j]/x;
                if(t>1 && t<mx)v.push_back(t);
            }
        }
        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

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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2120 KB Output is correct
2 Correct 0 ms 2120 KB Output is correct
3 Correct 0 ms 2120 KB Output is correct
4 Correct 3 ms 2392 KB Output is correct
5 Correct 3 ms 2392 KB Output is correct
6 Correct 39 ms 2120 KB Output is correct
7 Incorrect 6 ms 2452 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 2452 KB Output isn't correct
2 Halted 0 ms 0 KB -