Advertisement
Galebickosikasa

Untitled

May 11th, 2021
38
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.35 KB | None | 0 0
  1. // #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
  2. // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx")
  3.  
  4. #include <iostream>
  5. #include <vector>
  6. #include <cmath>
  7. #include <algorithm>
  8. #include <set>
  9. #include <map>
  10. #include <queue>
  11. #include <random>
  12. #include <chrono>
  13. #include <cassert>
  14. #include <sstream>
  15. #include <fstream>
  16. #include <iomanip>
  17. #include <tuple>
  18.  
  19. #define fi first
  20. #define se second
  21. #define pb push_back
  22. #define ll long long
  23. #define ld long double
  24. #define hm unordered_map
  25. #define pii pair<int, int>
  26. #define sz(a) (int)a.size()
  27. #define all(a) a.begin(), a.end()
  28. #define cinv(v) for (auto& x: v) cin >> x
  29. #define fr(i, n) for (int i = 0; i < (n); ++i)
  30. #define fl(i, l, n) for (int i = (l); i < (n); ++i)
  31.  
  32. #define int ll
  33.  
  34. template <typename T1, typename T2> inline bool chkmin(T1 &x, const T2 &y) {if (x > y) {x = y; return 1;} return 0;}
  35. template <typename T1, typename T2> inline bool chkmax(T1 &x, const T2 &y) {if (x < y) {x = y; return 1;} return 0;}
  36.  
  37. using namespace std;
  38.  
  39. #ifdef LOCAL
  40. #define dbg(x) cerr << #x << " : " << x << endl
  41. #else
  42. #define dbg(x)
  43. #endif
  44.  
  45. //tg: @runningcherry
  46.  
  47. template <typename Collection> string Join (const Collection& col) {
  48. bool first = true;
  49. stringstream ss;
  50. for (const auto& x: col) {
  51. if (!first) ss << ", ";
  52. first = false;
  53. ss << x;
  54. }
  55. return ss.str ();
  56. }
  57.  
  58. template <typename T1, typename T2> ostream& operator << (ostream& out, const pair<T1, T2>& v) {
  59. return out << '{' << v.fi << ", " << v.se << '}';
  60. }
  61.  
  62. template<typename T> ostream& operator << (ostream& out, const vector<T>& v) {
  63. return out << '[' << Join (v) << ']';
  64. }
  65.  
  66. template <typename T1, typename T2> ostream& operator << (ostream& out, const map<T1, T2>& v) {
  67. return out << '{' << Join (v) << '}';
  68. }
  69.  
  70. template<typename T> ostream& operator << (ostream& out, const set<T>& v) {
  71. return out << '(' << Join (v) << ')';
  72. }
  73.  
  74. template<typename T> ostream& operator << (ostream& out, const multiset<T>& v) {
  75. return out << '(' << Join (v) << ')';
  76. }
  77.  
  78. template <typename T1, typename T2> istream& operator >> (istream& in, pair<T1, T2>& a) {
  79. return in >> a.fi >> a.se;
  80. }
  81.  
  82. const ll inf = (ll) 2e9;
  83. const ll mod = (ll)1e9 + 7;
  84.  
  85. const int maxn = 11;
  86.  
  87. mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  88.  
  89. vector <pair <int, int>> d = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
  90. int goo[maxn][maxn], si = 5, sj = 5, dp[maxn][maxn];
  91.  
  92. int corr (int i, int j) {
  93. return i >= 0 && j >= 0 && i < maxn && j < maxn;
  94. }
  95.  
  96. int calc (vector <int> t) {
  97. for (auto& v: dp) for (auto& x: v) x = 0;
  98. queue <pair <int, int>> a;
  99. a.push ({si, sj});
  100. dp[si][sj] = goo[si][sj];
  101. pair <int, int> last;
  102. while (!a.empty ()) {
  103. auto ptt = a.front ();
  104. a.pop ();
  105. last = ptt;
  106. int i = ptt.first, j = ptt.second;
  107. for (auto& r: t) {
  108. auto x = d[r];
  109. int ii = i + x.first, jj = j + x.second;
  110. if (corr (ii, jj)) {
  111. chkmax (dp[ii][jj], dp[i][j] + goo[ii][jj]);
  112. a.push ({ii, jj});
  113. }
  114. }
  115. }
  116. return dp[last.first][last.second];
  117. }
  118.  
  119. signed main () {
  120. ios_base::sync_with_stdio (false);
  121. cin.tie (nullptr);
  122. for (auto& v: goo) for (auto& x: v) cin >> x;
  123.  
  124. vector <int> a = {calc ({0, 2}), calc ({0, 3}), calc ({1, 2}), calc ({1, 3})};
  125. sort (all (a));
  126. for (auto& x: a) cout << x << ' ';
  127. cout << '\n';
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134. }
  135.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement