oj.uz

Submission #22596

# Submission time Handle Problem Language Result Execution time Memory
22596 2017-04-30T05:49:57 Z 크리콘 B번 문제는 그리디로 풀려요(#918, imsifile) Unifying Values (KRIII5_UV) C++
0 / 7
 500 ms 3732 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], 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];
	}
	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

UV.cpp: In function 'int main()':
UV.cpp:25:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
UV.cpp:27:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &ba[i]), sum[i]=sum[i-1]+ba[i];
                                               ^

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1332 KB Output is correct
2 Correct 0 ms 1332 KB Output is correct
3 Correct 0 ms 1332 KB Output is correct
4 Correct 139 ms 3732 KB Output is correct
5 Correct 143 ms 3724 KB Output is correct
6 Execution timed out 500 ms 2412 KB Execution timed out
7 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 2500 KB Output is correct
2 Correct 66 ms 2104 KB Output is correct
3 Correct 63 ms 2108 KB Output is correct
4 Correct 146 ms 2256 KB Output is correct
5 Correct 389 ms 2916 KB Output is correct
6 Correct 396 ms 2652 KB Output is correct
7 Correct 176 ms 3168 KB Output is correct
8 Correct 99 ms 2364 KB Output is correct
9 Correct 9 ms 1464 KB Output is correct
10 Correct 0 ms 1332 KB Output is correct
11 Correct 0 ms 1332 KB Output is correct
12 Correct 0 ms 1332 KB Output is correct
13 Correct 3 ms 1332 KB Output is correct
14 Correct 3 ms 1332 KB Output is correct
15 Correct 3 ms 1332 KB Output is correct
16 Correct 3 ms 1332 KB Output is correct
17 Correct 143 ms 3728 KB Output is correct
18 Correct 149 ms 3724 KB Output is correct
19 Execution timed out 500 ms 2412 KB Execution timed out
20 Halted 0 ms 0 KB -