Submission #923629

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
923629	2024-02-07T13:50:14 Z	parlimoos	Jump (BOI06_jump)	C++14	100 / 100	21 ms	1388 KB

jump

//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include<array>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<ll , x>
#define endl '\n'

ll INF = (1ll * 1e14);

int n;
int mat[100][100];
arr(11) dp[100][100];
arr(11) zr = {0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0};

arr(11) Sum(arr(11) &a , arr(11) &b){
	arr(11) res = zr;
	for(int i = 0 ; i < 11 ; i++) res[i] = a[i] + b[i];
	for(int i = 0 ; i < 10 ; i++){
		ll d = res[i] % INF;
		res[i + 1] += (res[i] / INF);
		res[i] = d;
	}
	return res;
}
void f(int i , int j){
	if(dp[i][j] != zr) return;
	
	int jmp = mat[i][j];
	if(jmp == 0) return;
	if(i + jmp >= n and j + jmp >= n) return;
	if(i + jmp >= n) f(i , j + jmp) , dp[i][j] = dp[i][j + jmp];
	else if(j + jmp >= n) f(i + jmp , j) , dp[i][j] = dp[i + jmp][j];
	else{
		f(i + jmp , j) , f(i , j + jmp);
		dp[i][j] = Sum(dp[i + jmp][j] , dp[i][j + jmp]);
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for(int i = 0 ; i < n ; i++){
		for(int j = 0 ; j < n ; j++){
			cin >> mat[i][j];
		}
	}
	fill(&dp[0][0] , &dp[99][100] , zr);
	dp[n - 1][n - 1][0] = 1;
	f(0 , 0);
	int inx = 10;
	while(inx >= 0 and dp[0][0][inx] == 0) inx--;
	if(inx < 0) cout << 0;
	else{
		for(int i = inx ; i >= 0 ; i--){
			if(i == inx) cout << dp[0][0][i];
			else{
				ll dd = (1ll * 1e13);
				while(dp[0][0][i] < dd) dd /= 10 , cout << 0;
				cout << dp[0][0][i];
			}
		}
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1116 KB	Output is correct
2	Correct	1 ms	1116 KB	Output is correct
3	Correct	1 ms	1112 KB	Output is correct
4	Correct	1 ms	1112 KB	Output is correct
5	Correct	1 ms	1116 KB	Output is correct
6	Correct	1 ms	1116 KB	Output is correct
7	Correct	1 ms	1116 KB	Output is correct
8	Correct	1 ms	1116 KB	Output is correct
9	Correct	1 ms	1116 KB	Output is correct
10	Correct	1 ms	1128 KB	Output is correct
11	Correct	1 ms	1116 KB	Output is correct
12	Correct	1 ms	1116 KB	Output is correct
13	Correct	1 ms	1164 KB	Output is correct
14	Correct	1 ms	1112 KB	Output is correct
15	Correct	11 ms	1116 KB	Output is correct
16	Correct	1 ms	1252 KB	Output is correct
17	Correct	21 ms	1368 KB	Output is correct
18	Correct	1 ms	1372 KB	Output is correct
19	Correct	12 ms	1372 KB	Output is correct
20	Correct	2 ms	1388 KB	Output is correct