제출 #22846

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
22846		최숭실 (#40)	Unifying Values (KRIII5_UV)	C++14	0 / 7	306 ms	2176 KiB

UV

#include<iostream>
#include<algorithm>
#include<math.h>
#define MOD 1000000007
using namespace std;
long long int Data[10010];
long long int Sum[10010];
long long int ans;
long long int m_pow(long long int a, long long int b)
{
	long long int s = 1;
	for (long long int i = 0; i < b; i++)
	{
		s *= a;
		s %= MOD;
	}
	return s;
}
int main()
{
	long long int n;
	cin >> n;
	for (long long int i = 0; i < n; i++)
	{
		cin >> Data[i];
		if (i == 0)Sum[i] = Data[i];
		else
			Sum[i] = Sum[i - 1] + Data[i];
	}
	long long int target = 0;
	for (long long int i = 0; i < n - 1; i++)
	{
		target += Data[i];
		if (target == 0 && (Sum[n - 1] - Sum[i]) != 0)continue;
		if ((Sum[n - 1] - Sum[i]) < 0 && target > 0)continue;
		if ((Sum[n - 1] - Sum[i]) > 0 && target < 0)continue;
		if (target != 0 && (Sum[n - 1] - Sum[i]) % target != 0)continue;
		long long int Zero = 0;
		long long int tmp_sum = 0;
		long long int Zero_sum = 1;
		int flag = 0;
		if (target == 0)
		{
			for (long long int j = i + 1; j < n; j++)
			{
				if (Data[j] == 0)Zero++;
				else
				{
					tmp_sum += Data[j];
					if (tmp_sum == 0)Zero++;
				}
			}
			ans += (m_pow(2, Zero) - 1);
			ans %= MOD;
		}
		else
		{
			for (long long int j = i + 1; j < n; j++)
			{
				tmp_sum += Data[j];
				if (tmp_sum == target)
					tmp_sum = 0;
				if (Data[j] == 0)Zero++;
				else
				{
					if (flag == 0)
					{
						flag = 1;
						Zero = 0;
					}
					else if (flag == 1)
					{
						if (j == n - 1)continue;
						Zero_sum *= (Zero + 1);
						Zero = 0;
						Zero_sum %= MOD;
					}
				}
			}
			if (tmp_sum != 0)continue;
			ans += Zero_sum;
			ans %= MOD;
		}
	}
	cout << ans;
	return 0;
}

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