fork(2) download
copy 
  1. #include "bits/stdc++.h"
  2. #define sd(n) scanf("%d", &(n))
  3. #define rep(i, x, n) for (size_t i = x, _n = (n); i < _n; ++i)
  4. #define SZ(c) (int)(c).size()
  5. #define lcm(a,b) (a*(b/__gcd(a,b)))
  6. #define VI vector<int>
  7. #define all(c) ((c).begin(), (c).end())
  8. #define pb push_back
  9. #define pii pair<int, int>
  10. #define pip pair<int, pii>
  11. #define F first
  12. #define S second
  13. #define mp make_pair
  14. #define lli long long int
  15. #define CLR(p) memset(p, 0, sizeof(p))
  16. #define SET(p) memset(p, -1, sizeof(p))
  17. #define INF 0x3f3f3f3f
  18. using namespace std;
  19.  
  20. const int MOD = 1e9+7;
  21. const int MAX = 2001;
  22.  
  23. int dx[] = {0, -1, 1, 0};
  24. int dy[] = {1, 0, 0, -1};
  25.  
  26. char mat[2004][2004];
  27. int visited[2004][2004];
  28.  
  29. class TheGridDivTwo
  30. {
  31. public:
  32. 	int dfs(int p, int q, int k)
  33. 	{
  34. 		visited[p][q] = 1;
  35. 		if(k == 0)
  36. 		{
  37. 		 	return q;
  38. 		}
  39. 		int maxi = INT_MIN;
  40. 		rep(j, 0, 4)
  41. 		{
  42. 			int x = p + dx[j];
  43. 			int y = q + dy[j];
  44. 			if(x < 0 || y < 0 || x >= MAX || y >= MAX)
  45. 				continue;
  46.  
  47. 			if(mat[x][y] == '.' && !visited[x][y])
  48. 			{
  49. 				maxi = max(maxi, dfs(x, y, k-1));
  50. 			}
  51. 		}
  52. 		return maxi;
  53. 	}
  54. 	int find(vector <int> x, vector <int> y, int k)
  55. 	{
  56. 		int n =x.size();
  57. 		if(n == 0) return k;
  58.  
  59. 		rep(i, 0, MAX)
  60. 			rep(j, 0, MAX)
  61. 				mat[i][j] = '.';
  62. 		rep(i, 0, n)
  63. 			mat[1000-y[i]][1000+x[i]] = 'x';
  64.  
  65.  
  66. 		int ans = dfs(1000, 1000, k);
  67. 		if(ans == INT_MIN) return 0;
  68. 		return ans-1000;
  69. 	}
  70. };
  71.  
  72. int main()
  73. {
  74. 	TheGridDivTwo TG;
  75. 	int n, k;
  76. 	cin >> n;
  77. 	VI x(n), y(n);
  78. 	rep(i, 0, n)
  79. 		cin >> x[i];
  80. 	rep(i, 0, n)
  81. 		cin >> y[i];
  82.  
  83. 	cin >> k;
  84.  
  85. 	cout << TG.find(x, y, k) << endl;
  86.     return 0;
  87. }    
  88.  
Success #stdin #stdout 0s 22840KB
comments (?)
stdin
copy 
11
1 0 0 -1 -1 -2 -2 -3 -3 -4 -4
0 -1 1 -2 2 -3 3 -4 4 -5 5
47
stdout
copy 
31
https://ideone.com/nzWCiX
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!