Submission #307091

#	Time	Username	Problem	Language	Result	Execution time	Memory
307091		Rainbowbunny	Jump (BOI06_jump)	C++17	100 / 100	16 ms	2176 KiB

jump

#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
using namespace std;
using cd = complex <double>;
 
const long long INF = 1e15;
const int N = 3e5 + 2;
//const int mod = 1e9 + 7;//998244353;//1e9 + 7;//786433;
const double Pi = acos(-1);
 
void Fastio()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}
 
int n;
int a[105][105];
vector <int> dp[105][105];
 
vector <int> Add(vector <int> A, vector <int> B)
{
	int more = 0;
	vector <int> C;
	if(A.size() > B.size())
	{
		swap(A, B);
	}
	for(int i = 0; i < A.size(); i++)
	{
		int temp = B[i] + A[i] + more;
		if(temp >= 10)
		{
			temp -= 10;
			more = 1;
		}
		else
		{
			more = 0;
		}
		C.eb(temp);
	}
	for(int i = A.size(); i < B.size(); i++)
	{
		int temp = B[i] + more;
		if(temp >= 10)
		{
			temp -= 10;
			more = 1;
		}
		else
		{
			more = 0;
		}
		C.eb(temp);
	}
	if(more)
	{
		C.eb(more);
	}
	return C;
}
 
signed main()
{
	Fastio();
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			cin >> a[i][j];
			dp[i][j] = vector(1, 0);
		}
	}
	dp[1][1] = vector <int>(1, 1);
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			int nx = i + a[i][j], ny = j;
			vector <int> Temp = dp[i][j];
			if(a[i][j] == 0)
			{
				continue;
			}
			if(nx <= n)
			{
				dp[nx][ny] = Add(dp[nx][ny], dp[i][j]);
			}
			nx = i, ny = j + a[i][j];
			if(ny <= n)
			{
				dp[nx][ny] = Add(dp[nx][ny], dp[i][j]);
			}
		}
	}
	reverse(dp[n][n].begin(), dp[n][n].end());
	for(auto x : dp[n][n])
	{
		cout << x;
	}
}

Compilation message (stderr)

jump.cpp: In function 'std::vector<int> Add(std::vector<int>, std::vector<int>)':
jump.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i = 0; i < A.size(); i++)
      |                 ~~^~~~~~~~~~
jump.cpp:47:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int i = A.size(); i < B.size(); i++)
      |                        ~~^~~~~~~~~~

• Subtask 1: 100 / 100