Submission #22861

#TimeUsernameProblemLanguageResultExecution timeMemory
22861삼*전자 그린픽스 (#40)Unifying Values (KRIII5_UV)C++98
0 / 7
23 ms3640 KiB
#include<stdio.h> #include<algorithm> #include<set> #include<map> #include<vector> 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]; map<long long int, vector<int> > xx; set<long long int> ss; long long int ms[2 * I]; void update_ms(int i, long long int k) { ms[i + I] = k; i = i + I; i /= 2; while (i > 0) { ms[i] = (ms[i * 2] + ms[i * 2 + 1]) % M; i /= 2; } } long long int get_ms(int dep, int ql, int qr, int ll, int rr) { if (rr < ql || qr < ll) return 0; if (ql <= ll && rr <= qr) { return ms[dep]; } return (get_ms(dep * 2, ql, qr, ll, (ll + rr) / 2) + get_ms(dep * 2 + 1, ql, qr, (ll + rr) / 2 + 1, rr)) % M; } 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 = 0; i < 2 * I; i++) ms[i] = 0; for (i = 1; i <= n; i++) { if (s[i] == x) { update_ms(i, 1); } } if (m > 0) { xx.clear(); for (i = 1; i <= n; i++) { if (s[i] % x == 0 && s[i]/x>0) { xx[s[i]].push_back(i); } } for (k = 2; k <= m; k++) { long long int cur = k*x; for (i = ((int)xx[cur].size()) - 1; i >= 0; i--) { long long int kk = get_ms(1, 0, xx[cur][i], 0, I - 1); // printf("%lld %d --> %lld\n", cur, xx[cur][i], kk); update_ms(xx[cur][i], kk); } for (i = ((int)xx[cur-x].size()) - 1; i >= 0; i--) { update_ms(xx[cur-x][i], 0); } } res = ms[n + I]%M; } 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 (stderr)

UV.cpp: In function 'void process(long long int)':
UV.cpp:34:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, k, l;
         ^
UV.cpp:34:15: warning: unused variable 'l' [-Wunused-variable]
  int i, j, k, l;
               ^
UV.cpp:42:6: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
  int cur, nxt;
      ^
UV.cpp:42:11: warning: variable 'nxt' set but not used [-Wunused-but-set-variable]
  int cur, nxt;
           ^
UV.cpp:44:6: warning: unused variable 'si' [-Wunused-variable]
  int si = n+2;
      ^
UV.cpp: In function 'int main()':
UV.cpp:84:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, k, l;
         ^
UV.cpp:84:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k, l;
            ^
UV.cpp:84:15: warning: unused variable 'l' [-Wunused-variable]
  int i, j, k, l;
               ^
UV.cpp:85:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
UV.cpp:87:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a[i]);
                       ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...