| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 22614 | 2017-04-30T05:57:16 Z | 크리콘 B번 문제는 그리디로 풀려요(#918, imsifile) | Unifying Values (KRIII5_UV) | C++ | 500 ms | 3812 KB |
#include<stdio.h>
#include<map>
#define ab(a) ((a)<0?-(a):(a))
using namespace std;
typedef long long lld;
const lld mod = 1000000007;
int N, scn;
lld ba[10101], sum[10101], dyt[10101], dap;
map<pair<lld,int>, lld> dp;
lld dy(lld sm, int p){
pair<lld,int> pp = make_pair(sm, p);
if(p>N)return 1;
if(dp.find(pp) != dp.end()) return dp[pp];
lld dap=0;
for(int i=p; i<=N; i++){
if(sum[i]-sum[p-1] == sm) dap += dy(sm,i+1);
}
return dp[pp] = dap%mod;
}
int main(){
scanf("%d", &N);
for(int i=1; i<=N; i++){
scanf("%lld", &ba[i]), sum[i]=sum[i-1]+ba[i];
}
if(sum[N] == 0){
dyt[N+1]=1;
for(int i=N; i>=1; i--){
for(int j=i; j<=N; j++){
if(sum[j] == sum[i-1]) dyt[i] += dyt[j+1];
}
dyt[i] %= mod;
}
printf("%lld", (dyt[1]+mod-1)%mod);
return 0;
}
for(int i=1; i<=N; i++){
if(sum[N] == 0){
if(sum[i] == 0) dap += dy(0, i+1);
}
else{
if(sum[i] == 0)continue;
if(ab(sum[N]) % ab(sum[i]))continue;
if(sum[N] / sum[i] <= 0)continue;
dap += dy(sum[i], i+1);
}
}
printf("%lld", (dap+mod-1)%mod);
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 1412 KB | Output is correct |
| 2 | Correct | 0 ms | 1412 KB | Output is correct |
| 3 | Correct | 0 ms | 1412 KB | Output is correct |
| 4 | Correct | 143 ms | 3812 KB | Output is correct |
| 5 | Correct | 139 ms | 3812 KB | Output is correct |
| 6 | Correct | 66 ms | 1412 KB | Output is correct |
| 7 | Correct | 106 ms | 2584 KB | Output is correct |
| 8 | Correct | 93 ms | 2304 KB | Output is correct |
| 9 | Correct | 73 ms | 2184 KB | Output is correct |
| 10 | Correct | 146 ms | 2204 KB | Output is correct |
| 11 | Correct | 239 ms | 2336 KB | Output is correct |
| 12 | Correct | 96 ms | 1808 KB | Output is correct |
| 13 | Correct | 163 ms | 2848 KB | Output is correct |
| 14 | Correct | 96 ms | 2572 KB | Output is correct |
| 15 | Correct | 96 ms | 2440 KB | Output is correct |
| 16 | Correct | 136 ms | 2732 KB | Output is correct |
| 17 | Correct | 79 ms | 2204 KB | Output is correct |
| 18 | Correct | 153 ms | 1940 KB | Output is correct |
| 19 | Correct | 63 ms | 1412 KB | Output is correct |
| 20 | Correct | 56 ms | 1412 KB | Output is correct |
| 21 | Correct | 73 ms | 1412 KB | Output is correct |
| 22 | Correct | 149 ms | 1412 KB | Output is correct |
| 23 | Correct | 169 ms | 1412 KB | Output is correct |
| 24 | Correct | 156 ms | 1412 KB | Output is correct |
| 25 | Correct | 136 ms | 1412 KB | Output is correct |
| 26 | Correct | 119 ms | 1412 KB | Output is correct |
| 27 | Correct | 166 ms | 2204 KB | Output is correct |
| 28 | Correct | 329 ms | 2336 KB | Output is correct |
| 29 | Correct | 146 ms | 2600 KB | Output is correct |
| 30 | Correct | 459 ms | 3128 KB | Output is correct |
| 31 | Correct | 303 ms | 2732 KB | Output is correct |
| 32 | Correct | 289 ms | 2996 KB | Output is correct |
| 33 | Correct | 239 ms | 2732 KB | Output is correct |
| 34 | Correct | 236 ms | 2600 KB | Output is correct |
| 35 | Correct | 259 ms | 3128 KB | Output is correct |
| 36 | Correct | 323 ms | 3392 KB | Output is correct |
| 37 | Correct | 236 ms | 3524 KB | Output is correct |
| 38 | Correct | 253 ms | 3524 KB | Output is correct |
| 39 | Correct | 253 ms | 3524 KB | Output is correct |
| 40 | Correct | 193 ms | 2864 KB | Output is correct |
| 41 | Correct | 243 ms | 3392 KB | Output is correct |
| 42 | Correct | 133 ms | 2468 KB | Output is correct |
| 43 | Correct | 216 ms | 3524 KB | Output is correct |
| 44 | Correct | 153 ms | 2732 KB | Output is correct |
| 45 | Correct | 246 ms | 3392 KB | Output is correct |
| 46 | Correct | 246 ms | 3392 KB | Output is correct |
| 47 | Correct | 163 ms | 2996 KB | Output is correct |
| 48 | Correct | 156 ms | 2864 KB | Output is correct |
| 49 | Correct | 96 ms | 2336 KB | Output is correct |
| 50 | Correct | 163 ms | 3004 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 106 ms | 2576 KB | Output is correct |
| 2 | Correct | 63 ms | 2184 KB | Output is correct |
| 3 | Correct | 63 ms | 2188 KB | Output is correct |
| 4 | Correct | 139 ms | 2336 KB | Output is correct |
| 5 | Correct | 406 ms | 2996 KB | Output is correct |
| 6 | Correct | 386 ms | 2732 KB | Output is correct |
| 7 | Correct | 163 ms | 3244 KB | Output is correct |
| 8 | Correct | 93 ms | 2444 KB | Output is correct |
| 9 | Correct | 9 ms | 1544 KB | Output is correct |
| 10 | Correct | 0 ms | 1412 KB | Output is correct |
| 11 | Correct | 0 ms | 1412 KB | Output is correct |
| 12 | Correct | 0 ms | 1412 KB | Output is correct |
| 13 | Correct | 0 ms | 1412 KB | Output is correct |
| 14 | Correct | 3 ms | 1412 KB | Output is correct |
| 15 | Correct | 0 ms | 1412 KB | Output is correct |
| 16 | Correct | 0 ms | 1412 KB | Output is correct |
| 17 | Correct | 143 ms | 3808 KB | Output is correct |
| 18 | Correct | 143 ms | 3808 KB | Output is correct |
| 19 | Correct | 76 ms | 1412 KB | Output is correct |
| 20 | Correct | 56 ms | 1412 KB | Output is correct |
| 21 | Correct | 53 ms | 1412 KB | Output is correct |
| 22 | Correct | 56 ms | 1412 KB | Output is correct |
| 23 | Correct | 143 ms | 1412 KB | Output is correct |
| 24 | Correct | 106 ms | 1412 KB | Output is correct |
| 25 | Correct | 79 ms | 1412 KB | Output is correct |
| 26 | Correct | 69 ms | 1412 KB | Output is correct |
| 27 | Correct | 76 ms | 1808 KB | Output is correct |
| 28 | Correct | 39 ms | 1808 KB | Output is correct |
| 29 | Correct | 29 ms | 1836 KB | Output is correct |
| 30 | Correct | 36 ms | 1828 KB | Output is correct |
| 31 | Correct | 36 ms | 1956 KB | Output is correct |
| 32 | Correct | 39 ms | 1808 KB | Output is correct |
| 33 | Correct | 36 ms | 1808 KB | Output is correct |
| 34 | Correct | 36 ms | 1808 KB | Output is correct |
| 35 | Correct | 36 ms | 1808 KB | Output is correct |
| 36 | Correct | 29 ms | 1808 KB | Output is correct |
| 37 | Correct | 39 ms | 1808 KB | Output is correct |
| 38 | Correct | 36 ms | 1808 KB | Output is correct |
| 39 | Correct | 33 ms | 1808 KB | Output is correct |
| 40 | Correct | 66 ms | 2072 KB | Output is correct |
| 41 | Correct | 79 ms | 2204 KB | Output is correct |
| 42 | Correct | 49 ms | 1940 KB | Output is correct |
| 43 | Correct | 46 ms | 1940 KB | Output is correct |
| 44 | Correct | 83 ms | 2336 KB | Output is correct |
| 45 | Correct | 63 ms | 2072 KB | Output is correct |
| 46 | Correct | 9 ms | 1544 KB | Output is correct |
| 47 | Correct | 13 ms | 1544 KB | Output is correct |
| 48 | Correct | 13 ms | 1544 KB | Output is correct |
| 49 | Correct | 16 ms | 1544 KB | Output is correct |
| 50 | Correct | 16 ms | 1544 KB | Output is correct |
| 51 | Correct | 16 ms | 1544 KB | Output is correct |
| 52 | Correct | 3 ms | 1412 KB | Output is correct |
| 53 | Correct | 3 ms | 1412 KB | Output is correct |
| 54 | Correct | 3 ms | 1412 KB | Output is correct |
| 55 | Correct | 3 ms | 1412 KB | Output is correct |
| 56 | Correct | 3 ms | 1412 KB | Output is correct |
| 57 | Correct | 3 ms | 1412 KB | Output is correct |
| 58 | Correct | 6 ms | 1412 KB | Output is correct |
| 59 | Correct | 6 ms | 1412 KB | Output is correct |
| 60 | Correct | 6 ms | 1412 KB | Output is correct |
| 61 | Correct | 3 ms | 1412 KB | Output is correct |
| 62 | Correct | 3 ms | 1412 KB | Output is correct |
| 63 | Correct | 6 ms | 1412 KB | Output is correct |
| 64 | Correct | 56 ms | 2072 KB | Output is correct |
| 65 | Execution timed out | 500 ms | 2072 KB | Execution timed out |
| 66 | Halted | 0 ms | 0 KB | - |