Submission #290894

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
290894	2020-09-04 14:23:00	groeneprof	Fibonacci representations (CEOI18_fib)	C++14	15 / 100	4050 ms	6816 KiB

fib

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#define int long long
#define P(a) do{if(debug) cout<<a<<endl;} while(false)
#define H(a) P(#a<<": "<<a)
#define FR(i,a,b) for(int i = (a); i<(b); i++)
#define F(i,n) FR(i,0,n)
const int debug = 0;
const int mod = 1e9+7;
using namespace std;
vector<vector<int> > dp;
vector<int> a;
int X(int siz, int offset){ //offset is either -a[siz] or -a[siz]+1, 
  H(siz); H(offset);
  H(offset+a[siz]);
  if(siz==1) return ((a[0]+offset+1)/2)%mod; 
  if(dp[siz][offset+a[siz]]!=-1) return dp[siz][offset+a[siz]];
  dp[siz][offset+a[siz]] = (X(siz-1,offset-(a[siz-1]+offset)) + X(siz-1,offset-(a[siz-1]+offset)+1) * (X(1, a[siz-1]+offset-a[0])-1))%mod;
  H(siz); H(offset);
  H(offset+a[siz]);
  H(dp[siz][offset+a[siz]]);
  P("exit");
  return dp[siz][offset+a[siz]];
}
signed main(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 0 / 5
• Subtask 2: 0 / 20
• Subtask 3: 15 / 15
• Subtask 4: 0 / 10
• Subtask 5: 0 / 15
• Subtask 6: 0 / 35