Submission #316339

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
316339	2020-10-25T23:15:57 Z	sofapuden	Jump (BOI06_jump)	C++14	100 / 100	14 ms	1152 KB

jump

#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";
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	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