# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
22756 | King_God_OnionPringles (#40) | Unifying Values (KRIII5_UV) | C++98 | 500 ms | 392840 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define je 1000000007
int sum[10001];
int dp[10001][10001];
long long hap[10001];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
long long su;
scanf("%lld",&su);
hap[i] = hap[i-1] + su;
}
dp[n][1] = 1;
sum[n] = 1;
for(int i=n-1;i>=1;i--){
for(int j=i;j<n;j++){
long long happ = hap[n] - hap[j];
long long sub = hap[j] - hap[i-1];
if(sub == 0){
sum[i] = (sum[i] + sum[j+1]) % je;
}else{
if((happ > 0 && sub < 0) || (happ < 0 && sub > 0)) continue;
if(happ < 0 && sub < 0){ happ = -happ; sub = -sub;}
if(happ % sub == 0 && happ / sub <= n-j){
int pls = dp[j+1][happ / sub];
sum[i] = (sum[i] + pls) % je;
dp[i][happ / sub + 1] = (dp[i][happ / sub + 1] + pls) % je;
}
}
}
dp[i][1] = 1;
sum[i] = (sum[i] + 1) % je;
}
printf("%d", (sum[1] + je - 1) % je);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |