oj.uz

답안 #923596

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
923596 2024-02-07T13:19:06 Z parlimoos Jump (BOI06_jump) C++17
90 / 100
 15 ms 1116 KB 
//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'

const ll INF = (1ll * 1e17);

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

arr(6) Sum(arr(6) &a , arr(6) &b){
	arr(6) res;
	for(int i = 0 ; i < 6 ; i++) res[i] = a[i] + b[i];
	for(int i = 0 ; i < 5 ; 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;
	if(mat[i][j] == 0) return;
	if(i + mat[i][j] >= n and j + mat[i][j] >= n) return;
	if(i + mat[i][j] >= n) f(i , j + mat[i][j]) , dp[i][j] = dp[i][j + mat[i][j]];
	else if(j + mat[i][j] >= n) f(i + mat[i][j] , j) , dp[i][j] = dp[i + mat[i][j]][j];
	else{
		f(i + mat[i][j] , j) , f(i , j + mat[i][j]);
		dp[i][j] = Sum(dp[i + mat[i][j]][j] , dp[i][j + mat[i][j]]);
	}
}

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] = {1 , 0 , 0 , 0 , 0 , 0};
	f(0 , 0);
	int inx = 5;
	while(inx >= 0 and dp[0][0][inx] == 0) inx--;
	for(int i = inx ; i >= 0 ; i--) cout << dp[0][0][i];
}

Subtask #1
90.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Incorrect 0 ms 860 KB Output isn't correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 0 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 0 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 1112 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 7 ms 860 KB Output is correct
16 Correct 1 ms 860 KB Output is correct
17 Correct 15 ms 736 KB Output is correct
18 Correct 1 ms 860 KB Output is correct
19 Correct 8 ms 1116 KB Output is correct
20 Incorrect 1 ms 860 KB Output isn't correct