API tools faq
paste
Guest User

Untitled

a guest
Nov 4th, 2023
82
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.62 KB | None | 0 0
raw download clone embed print report
  1. #include<bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3.  
  4. //pragmas
  5. #pragma GCC optimize("03")
  6. #pragma GCC target("avx,avx2,fma")
  7. //#pragma GCC optimization("01, 02, 03, 0fast, unroll-loops") //Retard mode
  8. //#pragma GCC optimize("Ofast,unroll-loops,omit-frame-pointer,inline") //Optimization flags
  9. //#pragma GCC option("arch=native,tune=native,no-zero-upper") //Enable AVX
  10.  
  11. //types
  12. #define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  13. #define ll long long
  14. #define TYPE long long
  15. #define ppair pair<TYPE, TYPE>
  16. #define vecvec(a, i, j, x) vector<vector<TYPE>> a (i, vector<TYPE> (j, x))
  17. #define vecvecvec(a, i, j, k, x) vector<vector<vector<TYPE>>> a (i + 1, vector<vector<TYPE>>(j + 1, vector<TYPE>(k + 1, x)))
  18.  
  19. using namespace std;
  20. using namespace __gnu_pbds;
  21.  
  22. //random stuff
  23. #define all(a) a.begin(),a.end()
  24. #define endl "\n"
  25. #define pb push_back
  26. #define mp make_pair
  27. #define sz(x) (long long int)x.size()
  28. #define F first
  29. #define S second
  30. #define sp " "
  31. const ll inf = 0x3f3f3f3f, INF = 1e18;
  32. const int MOD = 1e9 + 7;
  33. const ll BIG_MOD = 489133282872437279; //use to decrease hash collision probability
  34.  
  35. typedef tree<long long int, null_type, less<long long int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; //for multiset, use less_equal and erase x in multiset a -> a.erase(a.find_by_order(a.order_of_key(x)))
  36. struct custom_hash {
  37. static uint64_t splitmix64(uint64_t x) {
  38. x += 0x9e3779b97f4a7c15;
  39. x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  40. x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  41. return x ^ (x >> 31);
  42. }
  43.  
  44. size_t operator()(uint64_t x) const {
  45. static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  46. return splitmix64(x + FIXED_RANDOM);
  47. }
  48. };
  49. #define safe_map unordered_map<long long, int, custom_hash>
  50. #define hashmap gp_hash_table<int, int, custom_hash>
  51.  
  52.  
  53. //debug
  54. void __print(int x) {cerr << x;}
  55. void __print(long x) {cerr << x;}
  56. void __print(long long x) {cerr << x;}
  57. void __print(unsigned x) {cerr << x;}
  58. void __print(unsigned long x) {cerr << x;}
  59. void __print(unsigned long long x) {cerr << x;}
  60. void __print(float x) {cerr << x;}
  61. void __print(double x) {cerr << x;}
  62. void __print(long double x) {cerr << x;}
  63. void __print(char x) {cerr << '\'' << x << '\'';}
  64. void __print(const char *x) {cerr << '\"' << x << '\"';}
  65. void __print(const string &x) {cerr << '\"' << x << '\"';}
  66. void __print(bool x) {cerr << (x ? "true" : "false");}
  67.  
  68. template<typename T, typename V>
  69. void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
  70. template<typename T>
  71. void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
  72. void _print() {cerr << "]\n";}
  73. template <typename T, typename... V>
  74. void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
  75. #ifndef ONLINE_JUDGE
  76. #define debug(x...) {cerr << "[" << #x << "] = ["; _print(x);}
  77. #define reach cerr<<"reached"<<endl
  78. #else
  79. #define debug(x...)
  80. #define reach
  81. #endif
  82.  
  83.  
  84. /*---------------------------------------------------------------------------------------------------------------------------*/
  85. ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
  86. ll expo(ll a, ll b, ll mod) {ll res = 1; while (b > 0) {if (b & 1)res = (res * a) % mod; a = (a * a) % mod; b = b >> 1;} return res;}
  87. void extendgcd(ll a, ll b, ll*v) {if (b == 0) {v[0] = 1; v[1] = 0; v[2] = a; return ;} extendgcd(b, a % b, v); ll x = v[1]; v[1] = v[0] - v[1] * (a / b); v[0] = x; return;} //pass an arry of size1 3
  88. ll mminv(ll a, ll b) {ll arr[3]; extendgcd(a, b, arr); return arr[0];} //for non prime b
  89. ll mminvprime(ll a, ll b) {return expo(a, b - 2, b);}
  90. bool revsort(ll a, ll b) {return a > b;}
  91. void swap(int &x, int &y) {int temp = x; x = y; y = temp;}
  92. ll combination(ll n, ll r, ll m, ll *fact, ll *ifact) {ll val1 = fact[n]; ll val2 = ifact[n - r]; ll val3 = ifact[r]; return (((val1 * val2) % m) * val3) % m;}
  93. void google(int t) {cout << "Case #" << t << ": ";}
  94. vector<ll> sieve(int n) {int*arr = new int[n + 1](); vector<ll> vect; for (ll i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (ll j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
  95. ll mod_add(ll a, ll b, ll m = MOD) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;}
  96. ll mod_mul(ll a, ll b, ll m = MOD) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;}
  97. ll mod_sub(ll a, ll b, ll m = MOD) {a = a % m; b = b % m; return (((a - b) % m) + m) % m;}
  98. ll mod_div(ll a, ll b, ll m = MOD) {a = a % m; b = b % m; return (mod_mul(a, mminvprime(b, m), m) + m) % m;} //only for prime m
  99. ll phin(ll n) {ll number = n; if (n % 2 == 0) {number /= 2; while (n % 2 == 0) n /= 2;} for (ll i = 3; i <= sqrt(n); i += 2) {if (n % i == 0) {while (n % i == 0)n /= i; number = (number / i * (i - 1));}} if (n > 1)number = (number / n * (n - 1)) ; return number;} //O(sqrt(N))
  100. void precision(int a) {cout << setprecision(a) << fixed;}
  101. ll ceil_div(ll x, ll y){return (x + y - 1) / y;}
  102. unsigned long long power(unsigned long long x,ll y, ll p){unsigned long long res = 1;x = x % p; while (y > 0){if (y & 1)res = (res * x) % p;y = y >> 1;x = (x * x) % p;}return res;}
  103. unsigned long long modInverse(unsigned long long n,int p){return power(n, p - 2, p);}
  104. ll nCr(ll n,ll r, ll p){if (n < r)return 0;if (r == 0)return 1;unsigned long long fac[n + 1];fac[0] = 1;for (int i = 1; i <= n; i++)fac[i] = (fac[i - 1] * i) % p;return (fac[n] * modInverse(fac[r], p) % p* modInverse(fac[n - r], p) % p)% p;}
  105. ll accumulate(const vector<long long int> &nums){ll sum = 0; for(auto x : nums) sum += x; return sum;}
  106. ll tmax(ll a, ll b, ll c = 0, ll d = -INF, ll e = -INF, ll f = -INF){return max(a, max(b, max(c, max(d, max(e, f)))));}
  107. int log2_floor(unsigned long long i) {return i ? __builtin_clzll(1) - __builtin_clzll(i) : -1;}
  108. string bin(ll n){return bitset<32>(n).to_string();}
  109. /*--------------------------------------------------------------------------------------------------------------------------*/
  110.  
  111. #define int int64_t
  112.  
  113. const int MAXN = 325;
  114.  
  115. int64_t a[MAXN][MAXN];
  116. bool vis[MAXN][MAXN];
  117. int64_t sd[MAXN][MAXN], ed[MAXN][MAXN];
  118. int64_t dp[5][MAXN][MAXN];
  119.  
  120. void clear_vis(int r, int c)
  121. {
  122. for(int i = 1; i <= r; i ++)
  123. for(int j = 1; j <= c; j ++)
  124. vis[i][j] = false;
  125. }
  126.  
  127. //code starts
  128. void main_()
  129. {
  130. #ifndef ONLINE_JUDGE
  131. freopen("input.txt", "r", stdin);
  132. freopen("output.txt", "w", stdout);
  133. freopen("output.txt", "w", stderr);
  134. #endif
  135.  
  136. int tt;
  137. cin >> tt;
  138. for(int t = 1; t <= tt; t ++)
  139. {
  140. int r, c;
  141. cin >> r >> c;
  142.  
  143. for(int i = 0; i <= r + 3; i ++)
  144. for(int j = 0; j <= c + 3; j ++)
  145. sd[i][j] = ed[i][j] = 0, dp[1][i][j] = dp[2][i][j] = dp[3][i][j] = dp[4][i][j] = INF;
  146.  
  147. for(int i = 1; i <= r; i ++)
  148. for(int j = 1; j <= c; j ++)
  149. cin >> a[i][j];
  150.  
  151. for(int i = 0; i < r + 3; i ++) vis[i][0] = vis[i][c + 1] = true;
  152. for(int j = 0; j < c + 3; j ++) vis[0][j] = vis[r + 1][j] = true;
  153.  
  154. clear_vis(r, c);
  155. function<void(int, int)> fcalc = [&](int x, int y)
  156. {
  157. if(!vis[x - 1][y] or !vis[x][y - 1]) return;
  158. vis[x][y] = true;
  159.  
  160. sd[x][y] = a[x][y] + max((int64_t)0, max(sd[x - 1][y], sd[x][y - 1]));
  161.  
  162. if(x != r) fcalc(x + 1, y);
  163. if(y != c) fcalc(x, y + 1);
  164. };
  165. fcalc(1, 1);
  166.  
  167. clear_vis(r, c);
  168. function<void(int, int)> rcalc = [&](int x, int y)
  169. {
  170. if(!vis[x + 1][y] or !vis[x][y + 1]) return;
  171. vis[x][y] = true;
  172.  
  173. ed[x][y] = a[x][y] + max((int64_t)0, max(ed[x + 1][y], ed[x][y + 1]));
  174.  
  175. if(x != 1) rcalc(x - 1, y);
  176. if(y != 1) rcalc(x, y - 1);
  177. };
  178. rcalc(r, c);
  179.  
  180. //now the main dp
  181. clear_vis(r, c);
  182. function<void(int, int)> calc = [&](int x, int y)
  183. {
  184. if(!vis[x - 1][y] or !vis[x][y + 1]) return;
  185. vis[x][y] = true;
  186.  
  187. //last cell was to the right (current is 1 or 3, last state was 1 or 4)
  188. // if(y != c)
  189. // {
  190. // calculate for current type 1
  191. dp[1][x][y] = min(dp[1][x][y], min(
  192. max(dp[1][x][y + 1], sd[x - 1][y] + ed[x + 1][y]),
  193. max(dp[4][x][y + 1], sd[x - 1][y] + ed[x + 1][y])
  194. ));
  195.  
  196. // calculate for current type 3
  197. dp[3][x][y] = min(dp[3][x][y], min(
  198. max(dp[1][x][y + 1], max(sd[x - 1][y], sd[x][y - 1]) + ed[x + 1][y + 1]),
  199. max(dp[4][x][y + 1], max(sd[x - 1][y], sd[x][y - 1]) + max(ed[x + 1][y + 1], ed[x][min(c + 1, y + 2)]))
  200. ));
  201. // }
  202.  
  203. // last cell was above (current is 2 or 4, last state was 2 or 3)
  204. // if(x != 1)
  205. // {
  206. // calculate for current type 2
  207. dp[2][x][y] = min(dp[2][x][y], min(
  208. max(dp[2][x - 1][y], sd[x][y - 1] + ed[x][y + 1]),
  209. max(dp[3][x - 1][y], sd[x][y - 1] + ed[x][y + 1])
  210. ));
  211.  
  212. // calculate for current type 4
  213. dp[4][x][y] = min(dp[4][x][y], min(
  214. max(dp[2][x - 1][y], sd[x - 1][y - 1] + max(ed[x + 1][y], ed[x][y + 1])),
  215. max(dp[3][x - 1][y], max(sd[max((int)0, x - 2)][y], sd[x - 1][y - 1]) + max(ed[x + 1][y], ed[x][y + 1]))
  216. ));
  217. // }
  218.  
  219. if(x != r) calc(x + 1, y);
  220. if(y != 1) calc(x, y - 1);
  221. };
  222. for(int type = 1; type <= 4; type ++)
  223. dp[type][1][c] = 0;
  224. calc(1, c);
  225.  
  226. int64_t ans = INF;
  227. for(int type = 1; type <= 4; type ++)
  228. ans = min(ans, dp[type][r][1]);
  229.  
  230. cout << "Case #" << t << ": " << ans << endl;
  231. }
  232. }
  233.  
  234.  
  235. /*
  236. 1: x x x
  237.  
  238. 2: x
  239. x
  240. x
  241.  
  242. 3: x x
  243. x
  244.  
  245. 4: x
  246. x x
  247. */
  248.  
  249. static void run_with_stack_size(void (*func)(void), size_t stsize)
  250. {
  251. char *stack, *send;
  252. stack = (char *)malloc(stsize);
  253. send = stack + stsize - 16;
  254. send = (char *)((uintptr_t)send / 16 * 16);
  255. asm volatile(
  256. "mov %%rsp, (%0)\n"
  257. "mov %0, %%rsp\n"
  258. :
  259. : "r"(send));
  260. func();
  261. asm volatile("mov (%0), %%rsp\n" : : "r"(send));
  262. free(stack);
  263. }
  264. int32_t main()
  265. {
  266. run_with_stack_size(main_, 1024 * 1024 * 1024); // run with a 1 GiB stack
  267. return 0;
  268. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!