Submission #22621

#	Time	Username	Problem	Language	Result	Execution time	Memory
22621		Jongwon Party (#40)	Unifying Values (KRIII5_UV)	C++14	7 / 7	323 ms	1312 KiB

UV

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

long long arr[10010];
long long sum[10010];
int cnt[10010];
const int mod = 1000000007;

int e(int a, int x)
{
    if(x == 0)
        return 1;
    if(x%2)
        return 1LL * a * e(a, x-1) % mod;
    int t = e(a, x/2);
    return 1LL * t * t % mod;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    int n, i, j;
    scanf("%d", &n);
    for(i = 1; i<=n; i++)
        scanf("%lld", &arr[i]);

    for(i = 1; i<=n; i++)
        sum[i] = sum[i-1] + arr[i];

    if(sum[n] == 0)
    {
        int c = 0;
        for(i = 1; i<=n; i++)
            if(sum[i] == 0)
                c++;

        if(c < 2)
        {
            printf("0");
            return 0;
        }

        printf("%d", (0LL + e(2, c-1) - 1 + mod) % mod);
        return 0;
    }

    int r = 0, mx;
    long long b, t;
    for(i = 1; i<n; i++)
    {
        if(sum[i] == 0 || sum[n]%sum[i] != 0)
            continue;

        b = sum[n]/sum[i];
        if(b < 2 || b > n-i+1)
            continue;

        cnt[1] = 1;
        mx = 1;
        for(j = i+1; j<=n; j++)
        {
            if(sum[j]%sum[i] != 0)
                continue;

            t = sum[j]/sum[i];
            if(t < 2 || t > b)
                continue;

            if(t == b && j != n)
                continue;

            cnt[t] = (0LL + cnt[t] + cnt[t - 1]) % mod;
            mx = std::max(0LL + mx, t);
        }

        r = (0LL + r + cnt[b]) % mod;
        for(j = 1; j<=mx; j++)
            cnt[j] = 0;
    }

    printf("%d", r);
    return 0;
}

Compilation message (stderr)

UV.cpp: In function 'int main()':
UV.cpp:49:55: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
         printf("%d", (0LL + e(2, c-1) - 1 + mod) % mod);
                                                       ^
UV.cpp:29:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
UV.cpp:31:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &arr[i]);
                               ^

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