Submission #22890

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
22890	2017-04-30T08:56:12 Z	sys7961	Unifying Values (KRIII5_UV)	C++11	0 / 7	3 ms	2444 KB

UV

#include<bits/stdc++.h>
using std::vector;
using std::pair;
const long long MOD = 1000000007;
std::set<long long> set;
long long arr[10010];
long long sum[10010];
long long cnt[10010];
long long abss(long long a) {
	if (a < 0)return -a;
	return a;
}
int sign(long long a) {
	if (a > 0)return 1;
	if (a < 0)return -1;
	return 0;
}
long long poww(long long a, long long b) {
	if (b == 0)return 1;
	long long tmp = pow(a, b / 2);
	if (b % 2 == 1)return (((tmp*tmp) % MOD)*a) % MOD;
	return (tmp*tmp) % MOD;
}
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &arr[i]);
		sum[i] = sum[i - 1] + arr[i];
	}
	long long p = sum[n];
	long long ans = 0;
	long long zero = 0;
	if (p < 0) {
		for (int i = 1; i <= n; i++) {
			sum[i] = -sum[i];
		}
		p = sum[n];
	}
	for (int i = 1; i <= n; i++) {
		if (sum[i] == 0)zero++;
		if (sum[i] != 0 && set.count(sum[i]) == 0) {
			if ( p%sum[i] == 0 && sign(p)==sign(sum[i])) {
				set.insert(sum[i]);
				long long k = p / sum[i];
				if (k > n || k == 1 || k<0)continue;
				for (int j = 1; j <= k; j++) {
					cnt[j] = 0;
				}
				cnt[0] = 1;
				for (int j = i; j <= n; j++) {
					if (sum[j] % sum[i] == 0 && sum[j]!=0 && sign(sum[j])==sign(sum[i])) {
						long long q = sum[j] / sum[i];
						assert(q >= 1);
						cnt[q] += cnt[q - 1];
						cnt[q] %= MOD;
					}
				}
				ans += cnt[k];
				ans %= MOD;

			}
		}
	}
	if(sum[n]==0)
		ans += poww(2, zero - 1) - 1;
	printf("%lld", ans);
}

Compilation message

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

Subtask #1

0 / 2.0

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

Subtask #2

0 / 5.0

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