Submission #22950

#	Time	Username	Problem	Language	Result	Execution time	Memory
22950		gs14004	Unifying Values (KRIII5_UV)	C++11	7 / 7	143 ms	3752 KiB

UV

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;
 
int n;
lint a[10005];
vector<int> v[10005];
vector<lint> dyn[10005];
 
lint dabs(lint x){ return max(x, -x); }
 
lint solve(int x){
	for(int i=0; i<=x; i++){
		v[i].clear();
		dyn[i].clear();
	}
	lint q = a[n] / x;
	for(int i=0; i<=n; i++){
		if(dabs(a[i]) % dabs(q) == 0){
			if(a[i] / q <= x && a[i]/q  >= 0) v[a[i] / q].push_back(i);
		}
	}
	for(int i=0; i<=x; i++){
		if(v[i].size() == 0) return 0;
		dyn[i].resize(v[i].size());
	}
	dyn[0][0] = 1;
	for(int i=1; i<=x; i++){
		int pt = 0;
		lint sum = 0;
		for(int j=0; j<v[i].size(); j++){
			while(pt < v[i-1].size() && v[i-1][pt] < v[i][j]){
				sum += dyn[i-1][pt];
				pt++;
			}
			sum %= mod;
			dyn[i][j] = sum;
		}
	}
	return dyn[x].back();
}
 
int main(){
	cin >> n;
	for(int i=1; i<=n; i++){
		lint x;
		cin >> x;
		a[i] = a[i-1] + x;
	}
	if(a[n] == 0){
		lint ans = 1;
		for(int i=1; i<n; i++){
			if(a[i] == 0) ans = ans * 2 % mod;
		}
		cout << (ans + mod - 1) % mod;
		return 0;
	}
	lint ret = 0;
	for(int i=2; i<=n; i++){
		if(dabs(a[n]) % i == 0){
			ret += solve(i);
		}
	}
	cout << ret % mod;
}

Compilation message (stderr)

UV.cpp: In function 'lint solve(int)':
UV.cpp:34:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<v[i].size(); j++){
                 ^
UV.cpp:35:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(pt < v[i-1].size() && v[i-1][pt] < v[i][j]){
             ^

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