oj.uz

Submission #22756

# Submission time Handle Problem Language Result Execution time Memory
22756 2017-04-30T07:14:40 Z King_God_OnionPringles(#981, mAng0) Unifying Values (KRIII5_UV) C++
0 / 7
 500 ms 392840 KB 
#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

UV.cpp: In function 'int main()':
UV.cpp:8:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
UV.cpp:11:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&su);
                          ^

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 392840 KB Output is correct
2 Correct 0 ms 392840 KB Output is correct
3 Correct 0 ms 392840 KB Output is correct
4 Execution timed out 500 ms 392840 KB Execution timed out
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 500 ms 392840 KB Execution timed out
2 Halted 0 ms 0 KB -