Submission #316338

#	Time	Username	Problem	Language	Result	Execution time	Memory
316338		sofapuden	Jump (BOI06_jump)	C++14	15 / 100	17 ms	1280 KiB

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);
	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: 15 / 100