Submission #64750131

Source Code Expand

#include <algorithm>
#include <iostream>

using namespace std;
typedef long long ll;

int n, k;
ll kbo[1010101];
ll sum[1010101];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> k;

	ll m = (ll)1e9;

	for (int i = 0; i < k; i++) {
		kbo[i] = 1;
		sum[i + 1] = (sum[i] + kbo[i]) % m;
	}

	for (int i = k; i <= n; i++) {
		kbo[i] = (sum[i] - sum[i - k] + m * 5) % m;
		sum[i + 1] = (sum[i] + kbo[i]) % m;
	}

	cout << kbo[n] << "\n";

	return 0;
}

Submission Info

Submission Time
Task C - K-bonacci
User minpro
Language C++ 20 (gcc 12.2)
Score 300
Code Size 502 Byte
Status AC
Exec Time 13 ms
Memory 19240 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 3
AC × 34
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1 ms 3480 KiB
00_sample_01.txt AC 1 ms 3444 KiB
00_sample_02.txt AC 12 ms 19068 KiB
01_random_00.txt AC 9 ms 17756 KiB
01_random_01.txt AC 9 ms 18832 KiB
01_random_02.txt AC 7 ms 14312 KiB
01_random_03.txt AC 12 ms 18032 KiB
01_random_04.txt AC 10 ms 14332 KiB
01_random_05.txt AC 9 ms 17304 KiB
01_random_06.txt AC 10 ms 18460 KiB
01_random_07.txt AC 12 ms 18660 KiB
01_random_08.txt AC 7 ms 14928 KiB
01_random_09.txt AC 12 ms 17460 KiB
01_random_10.txt AC 7 ms 14780 KiB
01_random_11.txt AC 4 ms 7904 KiB
01_random_12.txt AC 7 ms 11832 KiB
01_random_13.txt AC 2 ms 4408 KiB
01_random_14.txt AC 4 ms 9260 KiB
01_random_15.txt AC 4 ms 7964 KiB
01_random_16.txt AC 3 ms 7040 KiB
01_random_17.txt AC 9 ms 16552 KiB
01_random_18.txt AC 9 ms 16336 KiB
01_random_19.txt AC 1 ms 3704 KiB
01_random_20.txt AC 12 ms 19044 KiB
01_random_21.txt AC 12 ms 19096 KiB
01_random_22.txt AC 12 ms 19240 KiB
01_random_23.txt AC 12 ms 19076 KiB
01_random_24.txt AC 12 ms 19032 KiB
01_random_25.txt AC 1 ms 3472 KiB
01_random_26.txt AC 13 ms 19236 KiB
01_random_27.txt AC 13 ms 19020 KiB
01_random_28.txt AC 9 ms 19160 KiB
01_random_29.txt AC 9 ms 19096 KiB
01_random_30.txt AC 10 ms 19048 KiB