Submission #22311

# Submission time Handle Problem Language Result Execution time Memory
22311 2017-04-30T03:48:09 Z past future present(#977, kazel, pjh0123, nemo) Repeating Subsequence Tests (KRIII5_RST) C++14
0 / 7
0 ms 1332 KB
#include<stdio.h>
#include<string.h>
#include<set>
using namespace std;

const int mod = 1e9 + 7;

long long s[10000];
int n;

int modpow(long long a, long long b)
{
	return a*b%mod;
}

long long dp[10001];

long long cz(int i)
{
	if (i == n) return 1;
	if (dp[i] >= 0) return dp[i];
	dp[i] = 0;
	long long sum = 0;
	for (int j = i; j < n; j++)
	{
		sum += s[j];
		if (sum == 0)
		{
			dp[i] += cz(j + 1);
		}
	}
	dp[i] %= mod;
	return dp[i];
}

set<long long> v;

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%lld", s + i);
	memset(dp, -1, sizeof(dp));
	long long sum = 0, ans = cz(0);
	v.insert(0);
	for (int b = 0; b < n - 1; b++)
	{
		sum += s[b];
		if (v.find(sum) != v.end()) continue;
		v.insert(sum);
		long long ts = 0, z=0,zst=0, ta=1;
		for (int i = b + 1; i < n; i++)
		{
			ts += s[i];
			if (ts == sum)
			{
				ta = modpow(ta, zst + 1);
				ts = zst = 0;
			}
			else if (ts == 0)
			{
				zst++;
			}
		}
		if (ts != sum && ts != 0) ta = 0;
		ans += ta;
	}
	printf("%lld\n", ans%mod);
}

Compilation message

RST.cpp: In function 'int main()':
RST.cpp:51:21: warning: unused variable 'z' [-Wunused-variable]
   long long ts = 0, z=0,zst=0, ta=1;
                     ^
RST.cpp:40:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
RST.cpp:42:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", s + i);
                       ^
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1332 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1332 KB Output isn't correct
2 Halted 0 ms 0 KB -