oj.uz

Submission #128525

# Submission time Handle Problem Language Result Execution time Memory
128525 2019-07-11T05:49:51 Z 임유진(#3161) Fibonacci representations (CEOI18_fib) C++14
5 / 100
 451 ms 262144 KB 
#include <stdio.h>

typedef long long lint;

const int MOD = 1e9 + 7;
int A[15];
int fib[22];
lint dp[1000005][22];
int s[15];

int main() {
	int N;

	scanf("%d", &N);
	for(int i = 0; i < N; i++) scanf("%d", A + i);
	
	fib[1] = 1;
	fib[2] = 2;
	for(int i = 3; i < 22; i++) fib[i] = fib[i - 2] + fib[i - 1];

	for(int i = 1; i < 22; i++) dp[0][i] = dp[1][i] = 1ll;
	for(int i = 2; i < 1000000; i++) for(int j = 1; j < 22; j++)
		dp[i][j] = dp[i][j - 1] + (i >= fib[j] ? dp[i - fib[j]][j - 1] : 0ll);


	s[0] = fib[A[0]];
	for(int i = 1; i < N; i++) s[i] = s[i - 1] + fib[A[i]];
	
	for(int i = 0; i < N; i++) printf("%lld\n", dp[s[i]][21] % MOD);
	return 0;
}

Compilation message

fib.cpp: In function 'int main()':
fib.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
fib.cpp:15:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < N; i++) scanf("%d", A + i);
                             ~~~~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 172464 KB Output is correct
2 Correct 205 ms 172548 KB Output is correct
3 Correct 202 ms 172536 KB Output is correct
4 Correct 203 ms 172528 KB Output is correct
5 Correct 205 ms 172604 KB Output is correct
6 Correct 209 ms 172448 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 172464 KB Output is correct
2 Correct 205 ms 172548 KB Output is correct
3 Correct 202 ms 172536 KB Output is correct
4 Correct 203 ms 172528 KB Output is correct
5 Correct 205 ms 172604 KB Output is correct
6 Correct 209 ms 172448 KB Output is correct
7 Correct 222 ms 172520 KB Output is correct
8 Incorrect 209 ms 172480 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 207 ms 172496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 172464 KB Output is correct
2 Correct 205 ms 172548 KB Output is correct
3 Correct 202 ms 172536 KB Output is correct
4 Correct 203 ms 172528 KB Output is correct
5 Correct 205 ms 172604 KB Output is correct
6 Correct 209 ms 172448 KB Output is correct
7 Correct 222 ms 172520 KB Output is correct
8 Incorrect 209 ms 172480 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 451 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 172464 KB Output is correct
2 Correct 205 ms 172548 KB Output is correct
3 Correct 202 ms 172536 KB Output is correct
4 Correct 203 ms 172528 KB Output is correct
5 Correct 205 ms 172604 KB Output is correct
6 Correct 209 ms 172448 KB Output is correct
7 Correct 222 ms 172520 KB Output is correct
8 Incorrect 209 ms 172480 KB Output isn't correct
9 Halted 0 ms 0 KB -