답안 #316339

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
316339 2020-10-25T23:15:57 Z sofapuden Jump (BOI06_jump) C++14
100 / 100
14 ms 1152 KB
#include <bits/stdc++.h>

using namespace std;

string add(string a, string b){
	string ans;
	reverse(a.begin(),a.end());
	reverse(b.begin(),b.end());
	while(a.size() < b.size()){
		a+="0";
	}
	while(b.size() < a.size()){
		b+="0";
	}
	int ex = 0;
	for(int i = 0; i < (int)a.size(); ++i){
		int cur = a[i]+b[i]+ex-'0'-'0';
		ex = cur/10;
		ans+=(char)((cur%10)+'0');
	}
	if(ex)ans += (char)('0'+ex);
	reverse(ans.begin(),ans.end());
	return ans;
}
	

int main(){
	int n; cin >> n;
	vector<vector<int>> gr(n,vector<int>(n));
	vector<vector<string>> dp(n,vector<string>(n,"0"));
	dp[0][0] = "1";
	for(auto &x : gr)for(auto &y : x)cin >> y;
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			if(gr[i][j] + i < n && gr[i][j] != 0)dp[i+gr[i][j]][j]=add(dp[i][j],dp[i+gr[i][j]][j]);
			if(gr[i][j] + j < n && gr[i][j] != 0)dp[i][j+gr[i][j]]=add(dp[i][j],dp[i][j+gr[i][j]]);
		}
	}
	cout << dp[n-1][n-1] << "\n";
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 3 ms 512 KB Output is correct
16 Correct 8 ms 800 KB Output is correct
17 Correct 6 ms 640 KB Output is correct
18 Correct 10 ms 896 KB Output is correct
19 Correct 8 ms 768 KB Output is correct
20 Correct 14 ms 1152 KB Output is correct