답안 #22810

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
22810	2017-04-30T07:37:10 Z	삼*전자 그린픽스(#986, pichulia)	Unifying Values (KRIII5_UV)	C++	0 / 7	500 ms	1568 KB

UV

#include<stdio.h>
#include<algorithm>
#include<set>
using namespace std;
#define I 16384
#define M 1000000007
typedef pair<long long int, int> pii;
int n;
long long int a[10009];
long long int s[10009];
long long int res;
long long int d[2][10009];
long long int td[10009];
set<long long int> ss;
void process(long long int x) {
	int i, j, k, l;
	long long int m;
	if (s[n] == 0) m = -1;
	else {
		m = s[n] / x;
		if (m > n) return;
		if (m < 2) return;
	}
	int cur, nxt;
	cur = 0; nxt = 1;
	int si = n+2;
	for (i = 1; i <= n; i++)
	{
		if (s[i] == x)
		{
			d[0][i] = 1;
			if (si > i)si = i;
		}
		else
			d[0][i] = 0;
	}
	if (m > 0) {
		for (k = 2; k <= m; k++){
			long long int ss = 0;
			for (i = si; i <= n; i++) {
				d[nxt][i] = 0;
			}
			i = si;
			si = n + 2;
			for (; i <= n; i++) {
				if (s[i] == k*x)
				{
					d[nxt][i] = ss;
					if (d[nxt][i] > 0)if(i < si)si = i;
				}
				ss = (ss + d[cur][i]) % M;
			}

			i = cur;
			cur = nxt;
			nxt = i;
		}
		res = d[cur][n];
	}
	else
	{
		int ss = 0;
		for (i = 1; i < n; i++) { if (s[i] == 0)ss++; }
		res = 1;
		for (i = 0; i < ss; i++) { res = (res * 2) % M; }
		res = (res - 1 + M) % M;
	}
}
int main() {
	int i, j, k, l;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		s[i] = s[i - 1] + a[i];
	}
	for (i = 1; i < n; i++) {
		if (s[n] == 0 && s[i] == 0) {
			if (ss.find(s[i]) != ss.end()) continue;
			ss.insert(s[i]);
			process(0);
		}
		else if (s[i] != 0 && s[n] % s[i] == 0 && s[n] / s[i] > 1) {
			if (ss.find(s[i]) != ss.end()) continue;
			ss.insert(s[i]);
			process(s[i]);
		}
	}
	printf("%lld\n", res);
	return 0;
}

Compilation message

UV.cpp: In function 'void process(long long int)':
UV.cpp:16:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, k, l;
         ^
UV.cpp:16:15: warning: unused variable 'l' [-Wunused-variable]
  int i, j, k, l;
               ^
UV.cpp: In function 'int main()':
UV.cpp:70:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, k, l;
         ^
UV.cpp:70:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k, l;
            ^
UV.cpp:70:15: warning: unused variable 'l' [-Wunused-variable]
  int i, j, k, l;
               ^
UV.cpp:71:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
UV.cpp:73:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a[i]);
                       ^

Subtask #1

0 / 2.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1568 KB	Output is correct
2	Correct	0 ms	1568 KB	Output is correct
3	Correct	0 ms	1568 KB	Output is correct
4	Execution timed out	500 ms	1568 KB	Execution timed out
5	Halted	0 ms	0 KB	-

Subtask #2

0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	159 ms	1568 KB	Output isn't correct
2	Halted	0 ms	0 KB	-