Submission #3643091


Source Code Expand

#include<iostream>
using namespace std;

int fibdp[100010];
int n;

//フィボナッチ数列の第n項まで作る
int getfib(int n){
    if(n==0)return 1;
    if(n==1)return 2;
    if(fibdp[n]!=0)return fibdp[n];
    return fibdp[n]=getfib(n-1)+getfib(n-2);
}
int dp[100010];

int dfs(int k){
    if(k==0)return 0;
    if(dp[k]!=0)return dp[k];
    int ret=1000000;
    for(int i=0; i<n; i++){
        if(k<getfib(i))break;
        ret=min(ret,dfs(k-getfib(i))+1);
    }
    return dp[k]=ret;
}

int main(){
    cin>>n;
    
    cout<<dfs(n)<<endl;
}

Submission Info

Submission Time
Task A - ぶんたん
User izumo1627
Language C++14 (GCC 5.4.1)
Score 50
Code Size 583 Byte
Status RE
Exec Time 2104 ms
Memory 9984 KB

Judge Result

Set Name small large
Score / Max Score 50 / 50 0 / 50
Status
AC × 70
AC × 70
WA × 2
TLE × 2
RE × 55
Set Name Test Cases
small small/00_sample1, small/00_sample2, small/10_small_randomcase64, small/10_small_randomcase65, small/10_small_randomcase66, small/10_small_randomcase67, small/10_small_randomcase68, small/10_small_randomcase69, small/10_small_randomcase70, small/10_small_randomcase71, small/10_small_randomcase72, small/10_small_randomcase73, small/10_small_randomcase74, small/10_small_randomcase75, small/10_small_randomcase76, small/10_small_randomcase77, small/10_small_randomcase78, small/10_small_randomcase79, small/10_small_randomcase80, small/10_small_randomcase81, small/10_small_randomcase82, small/10_small_randomcase83, small/10_small_testcase00, small/10_small_testcase01, small/10_small_testcase02, small/10_small_testcase03, small/10_small_testcase04, small/10_small_testcase05, small/10_small_testcase06, small/10_small_testcase07, small/10_small_testcase08, small/10_small_testcase11, small/10_small_testcase12, small/10_small_testcase13, small/10_small_testcase14, small/10_small_testcase15, small/10_small_testcase16, small/10_small_testcase17, small/10_small_testcase18, small/10_small_testcase19, small/10_small_testcase20, small/10_small_testcase23, small/10_small_testcase24, small/10_small_testcase26, small/10_small_testcase28, small/10_small_testcase29, small/10_small_testcase31, small/10_small_testcase34, small/10_small_testcase36, small/10_small_testcase38, small/10_small_testcase39, small/10_small_testcase41, small/10_small_testcase42, small/10_small_testcase43, small/10_small_testcase44, small/10_small_testcase45, small/10_small_testcase46, small/10_small_testcase47, small/10_small_testcase48, small/10_small_testcase50, small/10_small_testcase51, small/10_small_testcase52, small/10_small_testcase53, small/10_small_testcase54, small/10_small_testcase56, small/10_small_testcase58, small/10_small_testcase59, small/10_small_testcase60, small/10_small_testcase61, small/10_small_testcase62
large small/00_sample1, small/00_sample2, small/10_small_randomcase64, small/10_small_randomcase65, small/10_small_randomcase66, small/10_small_randomcase67, small/10_small_randomcase68, small/10_small_randomcase69, small/10_small_randomcase70, small/10_small_randomcase71, small/10_small_randomcase72, small/10_small_randomcase73, small/10_small_randomcase74, small/10_small_randomcase75, small/10_small_randomcase76, small/10_small_randomcase77, small/10_small_randomcase78, small/10_small_randomcase79, small/10_small_randomcase80, small/10_small_randomcase81, small/10_small_randomcase82, small/10_small_randomcase83, small/10_small_testcase00, small/10_small_testcase01, small/10_small_testcase02, small/10_small_testcase03, small/10_small_testcase04, small/10_small_testcase05, small/10_small_testcase06, small/10_small_testcase07, small/10_small_testcase08, small/10_small_testcase11, small/10_small_testcase12, small/10_small_testcase13, small/10_small_testcase14, small/10_small_testcase15, small/10_small_testcase16, small/10_small_testcase17, small/10_small_testcase18, small/10_small_testcase19, small/10_small_testcase20, small/10_small_testcase23, small/10_small_testcase24, small/10_small_testcase26, small/10_small_testcase28, small/10_small_testcase29, small/10_small_testcase31, small/10_small_testcase34, small/10_small_testcase36, small/10_small_testcase38, small/10_small_testcase39, small/10_small_testcase41, small/10_small_testcase42, small/10_small_testcase43, small/10_small_testcase44, small/10_small_testcase45, small/10_small_testcase46, small/10_small_testcase47, small/10_small_testcase48, small/10_small_testcase50, small/10_small_testcase51, small/10_small_testcase52, small/10_small_testcase53, small/10_small_testcase54, small/10_small_testcase56, small/10_small_testcase58, small/10_small_testcase59, small/10_small_testcase60, small/10_small_testcase61, small/10_small_testcase62, large/20_large_randomcase128, large/20_large_randomcase129, large/20_large_randomcase130, large/20_large_randomcase131, large/20_large_randomcase132, large/20_large_randomcase133, large/20_large_randomcase134, large/20_large_randomcase135, large/20_large_randomcase136, large/20_large_randomcase137, large/20_large_randomcase138, large/20_large_randomcase139, large/20_large_randomcase140, large/20_large_randomcase141, large/20_large_randomcase142, large/20_large_randomcase143, large/20_large_randomcase144, large/20_large_randomcase145, large/20_large_randomcase146, large/20_large_randomcase147, large/20_large_testcase100, large/20_large_testcase101, large/20_large_testcase102, large/20_large_testcase103, large/20_large_testcase104, large/20_large_testcase105, large/20_large_testcase106, large/20_large_testcase107, large/20_large_testcase108, large/20_large_testcase109, large/20_large_testcase110, large/20_large_testcase111, large/20_large_testcase112, large/20_large_testcase113, large/20_large_testcase114, large/20_large_testcase115, large/20_large_testcase117, large/20_large_testcase118, large/20_large_testcase119, large/20_large_testcase120, large/20_large_testcase121, large/20_large_testcase122, large/20_large_testcase123, large/20_large_testcase124, large/20_large_testcase125, large/20_large_testcase126, large/20_large_testcase127, large/20_large_testcase84, large/20_large_testcase85, large/20_large_testcase86, large/20_large_testcase88, large/20_large_testcase89, large/20_large_testcase90, large/20_large_testcase91, large/20_large_testcase93, large/20_large_testcase95, large/20_large_testcase97, large/20_large_testcase98, large/20_sample3
Case Name Status Exec Time Memory
large/20_large_randomcase128 RE 103 ms 256 KB
large/20_large_randomcase129 RE 98 ms 256 KB
large/20_large_randomcase130 RE 99 ms 256 KB
large/20_large_randomcase131 RE 100 ms 256 KB
large/20_large_randomcase132 RE 101 ms 256 KB
large/20_large_randomcase133 RE 100 ms 256 KB
large/20_large_randomcase134 RE 100 ms 256 KB
large/20_large_randomcase135 RE 100 ms 256 KB
large/20_large_randomcase136 RE 99 ms 256 KB
large/20_large_randomcase137 RE 100 ms 256 KB
large/20_large_randomcase138 RE 102 ms 256 KB
large/20_large_randomcase139 RE 101 ms 256 KB
large/20_large_randomcase140 RE 98 ms 256 KB
large/20_large_randomcase141 RE 100 ms 256 KB
large/20_large_randomcase142 RE 100 ms 256 KB
large/20_large_randomcase143 RE 101 ms 256 KB
large/20_large_randomcase144 RE 100 ms 256 KB
large/20_large_randomcase145 RE 100 ms 256 KB
large/20_large_randomcase146 RE 100 ms 256 KB
large/20_large_randomcase147 RE 101 ms 256 KB
large/20_large_testcase100 RE 101 ms 256 KB
large/20_large_testcase101 RE 100 ms 256 KB
large/20_large_testcase102 RE 104 ms 256 KB
large/20_large_testcase103 RE 101 ms 256 KB
large/20_large_testcase104 RE 100 ms 256 KB
large/20_large_testcase105 RE 101 ms 256 KB
large/20_large_testcase106 RE 99 ms 256 KB
large/20_large_testcase107 RE 100 ms 256 KB
large/20_large_testcase108 RE 101 ms 256 KB
large/20_large_testcase109 RE 100 ms 256 KB
large/20_large_testcase110 RE 100 ms 256 KB
large/20_large_testcase111 RE 103 ms 256 KB
large/20_large_testcase112 WA 1070 ms 6656 KB
large/20_large_testcase113 RE 101 ms 256 KB
large/20_large_testcase114 RE 100 ms 256 KB
large/20_large_testcase115 RE 101 ms 256 KB
large/20_large_testcase117 RE 101 ms 256 KB
large/20_large_testcase118 RE 101 ms 256 KB
large/20_large_testcase119 RE 101 ms 256 KB
large/20_large_testcase120 RE 100 ms 256 KB
large/20_large_testcase121 RE 100 ms 256 KB
large/20_large_testcase122 TLE 2104 ms 9984 KB
large/20_large_testcase123 RE 100 ms 256 KB
large/20_large_testcase124 RE 102 ms 256 KB
large/20_large_testcase125 RE 101 ms 256 KB
large/20_large_testcase126 RE 101 ms 256 KB
large/20_large_testcase127 RE 101 ms 256 KB
large/20_large_testcase84 RE 101 ms 256 KB
large/20_large_testcase85 RE 101 ms 256 KB
large/20_large_testcase86 WA 753 ms 6400 KB
large/20_large_testcase88 RE 100 ms 256 KB
large/20_large_testcase89 RE 101 ms 256 KB
large/20_large_testcase90 RE 103 ms 256 KB
large/20_large_testcase91 RE 103 ms 256 KB
large/20_large_testcase93 RE 101 ms 256 KB
large/20_large_testcase95 RE 103 ms 256 KB
large/20_large_testcase97 RE 101 ms 256 KB
large/20_large_testcase98 TLE 2104 ms 9984 KB
large/20_sample3 RE 101 ms 256 KB
small/00_sample1 AC 1 ms 256 KB
small/00_sample2 AC 1 ms 256 KB
small/10_small_randomcase64 AC 3 ms 1024 KB
small/10_small_randomcase65 AC 5 ms 2560 KB
small/10_small_randomcase66 AC 10 ms 4864 KB
small/10_small_randomcase67 AC 6 ms 2944 KB
small/10_small_randomcase68 AC 5 ms 2176 KB
small/10_small_randomcase69 AC 7 ms 3456 KB
small/10_small_randomcase70 AC 5 ms 2560 KB
small/10_small_randomcase71 AC 3 ms 1280 KB
small/10_small_randomcase72 AC 5 ms 2432 KB
small/10_small_randomcase73 AC 6 ms 2688 KB
small/10_small_randomcase74 AC 2 ms 896 KB
small/10_small_randomcase75 AC 10 ms 4992 KB
small/10_small_randomcase76 AC 3 ms 1408 KB
small/10_small_randomcase77 AC 10 ms 4736 KB
small/10_small_randomcase78 AC 4 ms 1920 KB
small/10_small_randomcase79 AC 6 ms 2944 KB
small/10_small_randomcase80 AC 6 ms 2944 KB
small/10_small_randomcase81 AC 4 ms 1664 KB
small/10_small_randomcase82 AC 5 ms 2560 KB
small/10_small_randomcase83 AC 2 ms 896 KB
small/10_small_testcase00 AC 1 ms 256 KB
small/10_small_testcase01 AC 1 ms 256 KB
small/10_small_testcase02 AC 1 ms 256 KB
small/10_small_testcase03 AC 1 ms 256 KB
small/10_small_testcase04 AC 1 ms 256 KB
small/10_small_testcase05 AC 1 ms 256 KB
small/10_small_testcase06 AC 1 ms 256 KB
small/10_small_testcase07 AC 1 ms 256 KB
small/10_small_testcase08 AC 1 ms 256 KB
small/10_small_testcase11 AC 1 ms 256 KB
small/10_small_testcase12 AC 1 ms 256 KB
small/10_small_testcase13 AC 1 ms 256 KB
small/10_small_testcase14 AC 1 ms 256 KB
small/10_small_testcase15 AC 1 ms 256 KB
small/10_small_testcase16 AC 1 ms 256 KB
small/10_small_testcase17 AC 1 ms 256 KB
small/10_small_testcase18 AC 1 ms 256 KB
small/10_small_testcase19 AC 1 ms 256 KB
small/10_small_testcase20 AC 9 ms 4096 KB
small/10_small_testcase23 AC 1 ms 256 KB
small/10_small_testcase24 AC 2 ms 640 KB
small/10_small_testcase26 AC 1 ms 256 KB
small/10_small_testcase28 AC 1 ms 256 KB
small/10_small_testcase29 AC 3 ms 1152 KB
small/10_small_testcase31 AC 6 ms 2560 KB
small/10_small_testcase34 AC 1 ms 256 KB
small/10_small_testcase36 AC 1 ms 384 KB
small/10_small_testcase38 AC 1 ms 256 KB
small/10_small_testcase39 AC 1 ms 384 KB
small/10_small_testcase41 AC 6 ms 2560 KB
small/10_small_testcase42 AC 1 ms 256 KB
small/10_small_testcase43 AC 1 ms 256 KB
small/10_small_testcase44 AC 2 ms 640 KB
small/10_small_testcase45 AC 4 ms 1792 KB
small/10_small_testcase46 AC 6 ms 2944 KB
small/10_small_testcase47 AC 2 ms 512 KB
small/10_small_testcase48 AC 4 ms 1664 KB
small/10_small_testcase50 AC 1 ms 256 KB
small/10_small_testcase51 AC 1 ms 256 KB
small/10_small_testcase52 AC 1 ms 384 KB
small/10_small_testcase53 AC 2 ms 512 KB
small/10_small_testcase54 AC 6 ms 2688 KB
small/10_small_testcase56 AC 9 ms 4224 KB
small/10_small_testcase58 AC 1 ms 256 KB
small/10_small_testcase59 AC 1 ms 256 KB
small/10_small_testcase60 AC 1 ms 256 KB
small/10_small_testcase61 AC 1 ms 256 KB
small/10_small_testcase62 AC 8 ms 4096 KB