Submission #22301

#TimeUsernameProblemLanguageResultExecution timeMemory
22301- - - - - - - List of honorable mention follows - - - - - - - (#40)Unifying Values (KRIII5_UV)C++11
0 / 7
3 ms2256 KiB
#include <functional> #include <algorithm> #include <stdexcept> #include <iostream> #include <sstream> #include <fstream> #include <numeric> #include <iomanip> #include <cstdlib> #include <cstring> #include <utility> #include <cctype> #include <vector> #include <string> #include <bitset> #include <cmath> #include <queue> #include <stdint.h> #include <stdio.h> #include <stack> #include <ctime> #include <list> #include <map> #include <set> #include <tuple> #include <unordered_set> #include <assert.h> #define REP(i,n) for(int i=0;i<n;i++) #define TR(i,x) for(__typeof(x.begin()) i=x.begin();i!=x.end();i++) #define ALL(x) x.begin(),x.end() #define SORT(x) sort(ALL(x)) #define CLEAR(x) memset(x,0,sizeof(x)) #define FILL(x,c) memset(x,c,sizeof(x)) using namespace std; #define PB push_back #define MP make_pair typedef map<int,int> MII; typedef map<string,int> MSI; typedef vector<int> VI; typedef vector<string> VS; typedef vector<long double> VD; typedef pair<int,int> PII; typedef long long int64; typedef long long LL; typedef unsigned int UI; typedef long double LD; typedef unsigned long long ULL; const int N = 10007; const int MOD = 1000000007; LL a[N], sum[N]; LL dp[N]; int main() { int n; cin >> n; REP(i, n) cin >> a[i]; sum[0] = 0; for (int i = 0; i < n; ++i) { sum[i + 1] = sum[i] + a[i]; } set<LL> candidates; candidates.insert(sum[n]); if (sum[n] != 0) { for (int i = 1; i <= n; ++i) { if (sum[i] == 0) continue; if (sum[n] % sum[i] != 0) continue; LL steps = sum[n] / sum[i]; if (steps <= 0 || steps > n) { continue; } candidates.insert(sum[i]); } } LL answer = 0; if (sum[n] != sum[0]) { TR(it, candidates) { // cout << *it << endl; if (*it == sum[n]) continue; LL len = *it; LL maxStep = sum[n] / len; REP(i, maxStep + 1) dp[i] = 0; dp[0] = 1; for (int i = 1; i <= n; ++i) { if (sum[i] % len != 0) { continue; } LL step = sum[i] / len; // cout << "step is " << step << endl; if (step <= 0 || step > maxStep) { continue; } dp[step] += dp[step - 1]; if (dp[step] >= MOD) { dp[step] -= MOD; } } // REP(i, maxStep + 1) cout << dp[i] << ", "; cout << endl; answer = (answer + dp[maxStep]) % MOD; } } else { int zeros = 0; for (int i = 1; i < n; ++i) { if (sum[i] == 0) { ++zeros; } } if (zeros > 0) { answer = 1; for (int i = 0; i < zeros - 1; ++i) { answer = answer * 2 % MOD; } } } cout << answer << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...