oj.uz

Submission #128522

# Submission time Handle Problem Language Result Execution time Memory
128522 2019-07-11T05:48:27 Z 임유진(#3161) Fibonacci representations (CEOI18_fib) C++14
0 / 100
 413 ms 262144 KB 
#include <stdio.h>

typedef long long lint;

const int MOD = 1e9 + 7;
int A[15];
int fib[20];
lint dp[1000005][20];
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 < 20; i++) fib[i] = fib[i - 2] + fib[i - 1];

	for(int i = 1; i < 20; i++) dp[0][i] = dp[1][i] = 1ll;
	for(int i = 2; i < 1000000; i++) for(int j = 1; j < 20; 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]][19] % 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 156876 KB Output is correct
2 Correct 192 ms 156920 KB Output is correct
3 Correct 192 ms 156996 KB Output is correct
4 Correct 210 ms 156892 KB Output is correct
5 Correct 185 ms 156920 KB Output is correct
6 Incorrect 188 ms 156792 KB Output isn't correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 156876 KB Output is correct
2 Correct 192 ms 156920 KB Output is correct
3 Correct 192 ms 156996 KB Output is correct
4 Correct 210 ms 156892 KB Output is correct
5 Correct 185 ms 156920 KB Output is correct
6 Incorrect 188 ms 156792 KB Output isn't correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 156876 KB Output is correct
2 Correct 192 ms 156920 KB Output is correct
3 Correct 192 ms 156996 KB Output is correct
4 Correct 210 ms 156892 KB Output is correct
5 Correct 185 ms 156920 KB Output is correct
6 Incorrect 188 ms 156792 KB Output isn't correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 413 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 200 ms 156876 KB Output is correct
2 Correct 192 ms 156920 KB Output is correct
3 Correct 192 ms 156996 KB Output is correct
4 Correct 210 ms 156892 KB Output is correct
5 Correct 185 ms 156920 KB Output is correct
6 Incorrect 188 ms 156792 KB Output isn't correct