Submission #22883

#	Time	Username	Problem	Language	Result	Execution time	Memory
22883		AJAE (#40)	Unifying Values (KRIII5_UV)	C++14	0 / 7	6 ms	2700 KiB

UV

#include <iostream>
#include <set>
#include <algorithm>
#include <vector>

#define MOD 1000000007
#define ll long long

using namespace std;

ll d[10005];
ll nu[10005];
ll fact[10005] = { 1,1 };

int main() {
	for (int i = 2; i <= 10000; i++)
		fact[i] = (fact[i - 1] * i) % MOD;

	int n; 
	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {
		scanf("%lld", &d[i]);
		nu[i] = nu[i - 1] + d[i];
	}
	ll ans = 0;
	int zerochk = 0;
	set <int> chk;

	for (int i = 1; i < n; i++) {
		if (chk.find(nu[i]) != chk.end()) continue;
		chk.insert(nu[i]);

		ll s = nu[i];

		if (s == 0) {
			int count = 0;
			ll nz = 0;
			for (int j = i + 1; j < n; j++) {
				nz += d[i];
				if (nz == 0) count++;
			}
			ans = (ans + fact[count]) % MOD;
		}
		else {
			if (nu[n] / s > n - i + 1 || nu[n] % s != 0)
				continue;

			if ( nu[n] == s) continue;

			ll fin = 1;
			
			vector<ll> next(n + 1), dp(n + 1);

			dp[0] = dp[1] = 1;
			next[0] = next[1] = 1;

			for (int j = i + 1; j <= n; j++) {
				if (nu[j] % s == 0) {
					ll x = nu[j] / s;
					if (x < 1) continue;
					if (x <= fin + 1) {
						dp[x] = next[x - 1];
						next[x] += dp[x];
						fin = max(x, fin);
					}
				}
			}

			ans = (ans + dp[nu[n] / s]);
		}
	}
	printf("%lld", ans);
}

Compilation message (stderr)

UV.cpp: In function 'int main()':
UV.cpp:27:6: warning: unused variable 'zerochk' [-Wunused-variable]
  int zerochk = 0;
      ^
UV.cpp:20:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
UV.cpp:23:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &d[i]);
                       ^

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