Submission #22355

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
22355	2017-04-30T04:10:45 Z	past future present(#977, kazel, pjh0123, nemo)	Unifying Values (KRIII5_UV)	C++	0 / 7	500 ms	1472 KB

UV

#include<stdio.h>
#include<string.h>
#include<set>
#include<vector>
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];
}

long long foo(vector<int> &st)
{
	long long ans = 1;
	int z = 0;
	bool ok = false;
	for (int i : st)
	{
		if (i == 1)
		{
			ans = modpow(ans, z + 1);
			z = 0;
			ok = true;
		}
		else z++;
	}
	return ok?ans:0;
}

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);
	for (int i = 0; i < n; i++) sum += s[i];
	if (sum == 0) ans--;
	sum = 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;
		vector<int> st;
		int ncnt=0;
		for (int i = b + 1; i < n; i++)
		{
			ts += s[i];
			if (ts == sum)
			{
				if (ncnt)
				{
					while (!st.empty())
					{
						int t = st.back();
						st.pop_back();
						if (t == -1)
						{
							ncnt--;
							break;
						}
					}
				}
				else st.push_back(1);
				ts = 0;
			}
			else if (ts == -sum)
			{
				while (!st.empty())
				{
					int t = st.back();
					if (t == 1)
					{
						st.pop_back();
						st.push_back(0);
						break;
					}
					else if (t == 0)
					{
						st.pop_back();
					}
					else if (t == -1)
					{
						st.push_back(-1);
						ncnt++;
						break;
					}
				}
				ts = 0;
			}
			else if (ts == 0)
			{
				st.push_back(0);
			}
		}
		if(ncnt == 0 && ts == 0) ans += foo(st);
	}
	printf("%lld\n", ans%mod);
}

Compilation message

UV.cpp: In function 'long long int foo(std::vector<int>&)':
UV.cpp:42:15: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
  for (int i : st)
               ^
UV.cpp: In function 'int main()':
UV.cpp:59:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
UV.cpp:61:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", s + i);
                       ^
UV.cpp: In function 'long long int foo(std::vector<int>&)':
UV.cpp:44:3: warning: 'i' is used uninitialized in this function [-Wuninitialized]
   if (i == 1)
   ^

Subtask #1

0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1332 KB	Output is correct
2	Correct	0 ms	1332 KB	Output is correct
3	Correct	0 ms	1332 KB	Output is correct
4	Execution timed out	500 ms	1472 KB	Execution timed out
5	Halted	0 ms	0 KB	-

Subtask #2

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	500 ms	1332 KB	Execution timed out
2	Halted	0 ms	0 KB	-