Submission #64748233

Source Code Expand

#include <bits/stdc++.h>
 
using namespace std;

const int MOD=1e9;


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	int n,k;
	cin>>n>>k;
	
	
	
	if(n<k){
		cout<<1;
		return 0;
		
	}
	vector<long long> v(n+1);
	
	
	
	for(int i=0; i<k; i++) v[i]=1;
	long long tot=k;
	for(int i=k; i<=n; i++){
		v[i]=tot;
		
		tot+=v[i];
		tot-=v[i-k];
		tot%=MOD;
		if(tot<0) tot+=MOD; 
		
	}
	cout<<v[n]; 
	
	
    return 0;
}

Submission Info

Submission Time
Task C - K-bonacci
User usernameson
Language C++ 20 (gcc 12.2)
Score 300
Code Size 465 Byte
Status AC
Exec Time 9 ms
Memory 11044 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 3584 KiB
00_sample_01.txt AC 1 ms 3552 KiB
00_sample_02.txt AC 7 ms 10916 KiB
01_random_00.txt AC 1 ms 3504 KiB
01_random_01.txt AC 1 ms 3432 KiB
01_random_02.txt AC 1 ms 3368 KiB
01_random_03.txt AC 8 ms 10604 KiB
01_random_04.txt AC 6 ms 8568 KiB
01_random_05.txt AC 1 ms 3504 KiB
01_random_06.txt AC 6 ms 10616 KiB
01_random_07.txt AC 8 ms 10648 KiB
01_random_08.txt AC 1 ms 3552 KiB
01_random_09.txt AC 8 ms 10132 KiB
01_random_10.txt AC 4 ms 8580 KiB
01_random_11.txt AC 3 ms 5352 KiB
01_random_12.txt AC 5 ms 7276 KiB
01_random_13.txt AC 1 ms 3568 KiB
01_random_14.txt AC 3 ms 6024 KiB
01_random_15.txt AC 2 ms 5592 KiB
01_random_16.txt AC 2 ms 4964 KiB
01_random_17.txt AC 6 ms 9692 KiB
01_random_18.txt AC 5 ms 9428 KiB
01_random_19.txt AC 1 ms 3592 KiB
01_random_20.txt AC 8 ms 10912 KiB
01_random_21.txt AC 7 ms 11036 KiB
01_random_22.txt AC 7 ms 10968 KiB
01_random_23.txt AC 8 ms 10972 KiB
01_random_24.txt AC 7 ms 11036 KiB
01_random_25.txt AC 1 ms 3500 KiB
01_random_26.txt AC 9 ms 11044 KiB
01_random_27.txt AC 9 ms 10984 KiB
01_random_28.txt AC 1 ms 3420 KiB
01_random_29.txt AC 5 ms 10988 KiB
01_random_30.txt AC 1 ms 3496 KiB