Submission #22522

#	Time	Username	Problem	Language	Result	Execution time	Memory
22522		팀명을 한번 정하면 못바꿀까? (#40)	Unifying Values (KRIII5_UV)	C++14	7 / 7	13 ms	1644 KiB

UV

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <functional>
#include <set>
#include <map>
#include <queue>
#include <tuple>
#include <string.h>

using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
typedef long long ll;
typedef pair<int, int> pi;

const int MOD = 1e9 + 7, MAX_N = 1e4 + 10;

int N; ll Nr[MAX_N], Sum[MAX_N];
int Cnt[MAX_N];
vector<ll> list;
int getIx(ll v) {return lower_bound(list.begin(), list.end(), v) - list.begin();}
bool welldiv(ll a, ll b) {
	if(b == 0) return a == 0;
	return abs(a) % abs(b) == 0;
}
int main() {
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%lld", &Nr[i]), list.push_back(Sum[i] = Sum[i-1] + Nr[i]);
	list.push_back(0), sort(list.begin(), list.end()); list.erase(unique(list.begin(), list.end()), list.end());

	ll all = Sum[N], ans = 0;
	for(ll val : list) {
		if(welldiv(all, val) == false) continue;
		if(all == 0 && val != 0) continue;
		for(int i=0; i<=N; i++) Cnt[i] = 0;
		Cnt[getIx(0)] = 1;
		ll nowAns = 0;
		for(int i=1; i<=N; i++) {
			if(welldiv(Sum[i], val) == false) continue;
			ll pre = Sum[i] - val;
			int ix = getIx(Sum[i]), pix = getIx(pre);
			if(list[pix] != pre) continue;
			if(i == N) nowAns += Cnt[pix], nowAns %= MOD;
			Cnt[ix] += Cnt[pix]; Cnt[ix] %= MOD;
//			printf("%lld : %d\n", Sum[i], Cnt[ix]);
		}
//		printf("%lld : %d\n", val, nowAns);
		ans += nowAns; ans %= MOD;
	}
	ans += (MOD - 1); ans %= MOD;
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

UV.cpp: In function 'int main()':
UV.cpp:28:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
UV.cpp:29:90: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=N; i++) scanf("%lld", &Nr[i]), list.push_back(Sum[i] = Sum[i-1] + Nr[i]);
                                                                                          ^

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