답안 #307091

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
307091	2020-09-27T02:07:19 Z	Rainbowbunny	Jump (BOI06_jump)	C++17	100 / 100	16 ms	2176 KB

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

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.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	640 KB	Output is correct
2	Correct	1 ms	640 KB	Output is correct
3	Correct	1 ms	640 KB	Output is correct
4	Correct	1 ms	640 KB	Output is correct
5	Correct	1 ms	768 KB	Output is correct
6	Correct	1 ms	640 KB	Output is correct
7	Correct	1 ms	640 KB	Output is correct
8	Correct	1 ms	640 KB	Output is correct
9	Correct	1 ms	640 KB	Output is correct
10	Correct	1 ms	640 KB	Output is correct
11	Correct	1 ms	640 KB	Output is correct
12	Correct	1 ms	640 KB	Output is correct
13	Correct	2 ms	640 KB	Output is correct
14	Correct	2 ms	768 KB	Output is correct
15	Correct	4 ms	896 KB	Output is correct
16	Correct	9 ms	1536 KB	Output is correct
17	Correct	7 ms	1152 KB	Output is correct
18	Correct	12 ms	1792 KB	Output is correct
19	Correct	10 ms	1408 KB	Output is correct
20	Correct	16 ms	2176 KB	Output is correct