Submission #5849100


Source Code Expand

Copy
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        List<Integer> holeList  = new ArrayList<>();

        for (int i = 0; i < m; i++){
            holeList.add(sc.nextInt());
        }

        long count = 0;
        long countOneBefore = 1;
        long countTwoBefore = 0;

        int holeIndex = 0;
        int holeStair = 0;
        if (holeList.size() != 0){
            holeStair = holeList.get(holeIndex);
        }

        for (int i = 0 ; i < n; i++){

            if (holeStair == (i + 1)){
                // 穴が開いている場合
                count = 0;
                countTwoBefore = countOneBefore;
                countOneBefore = count;

                holeIndex += 1;
                holeStair = holeList.get(Math.min(holeIndex, m - 1));
            }else {
                count = countOneBefore + countTwoBefore;
                if (count >= 1000000007L){
                    count = count % 1000000007L;
                }
                countTwoBefore = countOneBefore;
                countOneBefore = count;
            }
        }

        System.out.println(count);
    }

}

Submission Info

Submission Time
Task C - Typical Stairs
User alkwest
Language Java8 (OpenJDK 1.8.0)
Score 300
Code Size 1311 Byte
Status
Exec Time 436 ms
Memory 59400 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 300 / 300 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 95 ms 19028 KB
02.txt 96 ms 19924 KB
03.txt 95 ms 21716 KB
04.txt 96 ms 22608 KB
05.txt 97 ms 19540 KB
06.txt 96 ms 18644 KB
07.txt 96 ms 19796 KB
08.txt 95 ms 18900 KB
09.txt 96 ms 21844 KB
10.txt 96 ms 19156 KB
11.txt 95 ms 18644 KB
12.txt 98 ms 19284 KB
13.txt 94 ms 19796 KB
14.txt 96 ms 21844 KB
15.txt 96 ms 21716 KB
16.txt 405 ms 46372 KB
17.txt 162 ms 27852 KB
18.txt 253 ms 38564 KB
19.txt 243 ms 35732 KB
20.txt 117 ms 21204 KB
21.txt 250 ms 40088 KB
22.txt 115 ms 21716 KB
23.txt 257 ms 39264 KB
24.txt 194 ms 30236 KB
25.txt 192 ms 27448 KB
26.txt 111 ms 20560 KB
27.txt 139 ms 24020 KB
28.txt 436 ms 59400 KB
29.txt 347 ms 48836 KB
30.txt 150 ms 25580 KB
31.txt 253 ms 38576 KB
32.txt 314 ms 42824 KB
33.txt 351 ms 46176 KB
s1.txt 95 ms 21844 KB
s2.txt 96 ms 19796 KB
s3.txt 96 ms 20948 KB