Advertisement
GerONSo

Untitled

Dec 29th, 2018
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.33 KB | None | 0 0
  1. /*
  2. ┓┏┓┏┓┃
  3. ┛┗┛┗┛┃
  4. ┓┏┓┏┓┃
  5. ┛┗┛┗┛┃
  6. ┓┏┓┏┓┃\○/
  7. ┛┗┛┗┛┃ / /
  8. ┓┏┓┏┓┃ノ
  9. ┛┗┛┗┛┃
  10. ┓┏┓┏┓┃
  11. ┛┗┛┗┛┃
  12. ┓┏┓┏┓┃
  13. ┛┗┛┗┛┃
  14. ┓┏┓┏┓┃
  15. ┛┗┛┗┛┃
  16. ┓┏┓┏┓┃┓
  17. ┛┗┛┗┛┃┃
  18. MIPTCLASSICMIPTCLASSICMIPTCLASSICMIPTCLASSICMIPTCLASSICMIPTCLASSIC
  19. */
  20.  
  21. // #define pragma
  22.  
  23. #ifdef pragma
  24. #pragma GCC optimize("Ofast")
  25. #pragma GCC optimize("no-stack-protector")
  26. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  27. #pragma GCC optimize("unroll-loops")
  28. #pragma GCC diagnostic ignored "-Wunused-result"
  29. #endif // pragma
  30.  
  31. #include<bits/stdc++.h>
  32. #include <ext/pb_ds/assoc_container.hpp>
  33. #include <ext/pb_ds/tree_policy.hpp>
  34.  
  35. #define ll long long
  36. #define all(x) begin(x), end(x)
  37. #define pb push_back
  38. #define x first
  39. #define y second
  40. #define int long long
  41. #define zero(two) memset(two, 0, sizeof(two))
  42.  
  43. using namespace std;
  44. using namespace __gnu_pbds;
  45.  
  46.  
  47. typedef vector<int> vi;
  48. typedef vector<bool> vb;
  49. typedef pair<int, int> pii;
  50. typedef long double ld;
  51. typedef vector<vi> matrix;
  52. template<typename T>
  53. using kawaii_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  54.  
  55. const ld PI = atan2(0, -1);
  56.  
  57. void seriy() {
  58. ios::sync_with_stdio(0);
  59. cin.tie(0);
  60. cout.tie(0);
  61. cout << fixed << setprecision(10);
  62. #if _offline
  63. freopen("input", "r", stdin);
  64. freopen("output", "w", stdout);
  65. #endif
  66. }
  67.  
  68. const int INF = 1e9 + 7;
  69. const int MAXN = 101;
  70.  
  71.  
  72. signed main() {
  73. seriy();
  74. // int n;
  75. // cin >> n;
  76. // vi tmp(n);
  77. // for(int i = 0; i < n; i++) {
  78. // cin >> tmp[i];
  79. // }
  80. // stack<int> indl, indr;
  81. // vi ml(n), mr(n);
  82. // for(int i = 0; i < n; i++) {
  83. // while(indl.size() && tmp[indl.top()] >= tmp[i]) {
  84. // indl.pop();
  85. // }
  86. // ml[i] = ((!indl.size()) ? 0 : indl.top() + 1);
  87. // indl.push(i);
  88. // }
  89. // for(int i = n - 1; i >= 0; i--) {
  90. // while(indr.size() && tmp[indr.top()] >= tmp[i]) {
  91. // indr.pop();
  92. // }
  93. // mr[i] = ((!indr.size()) ? n - 1 : indr.top() - 1);
  94. // indr.push(i);
  95. // }
  96. int a, b, c;
  97. cin >> a >> b >> c;
  98. if(a > 40 || b > 40 || c > 40) {
  99. assert(0);
  100. }
  101. vi log(MAXN);
  102. for(int i = 1; i < MAXN; i++) {
  103. int cnt = 0;
  104. while((1 << (cnt + 1)) < i) {
  105. cnt++;
  106. }
  107. log[i] = cnt;
  108. cerr << i << " " << log[i] << '\n';
  109. }
  110. bool m[a][b][c];
  111. int d[b][c];
  112. for(int j = 0; j < b; j++) {
  113. for(int k = 0; k < c; k++) {
  114. d[j][k] = -1;
  115. }
  116. }
  117. for(int i = 0; i < a; i++) {
  118. for(int j = 0; j < b; j++) {
  119. for(int k = 0; k < c; k++) {
  120. char ch;
  121. cin >> ch;
  122. m[i][j][k] = (ch == '1');
  123. }
  124. }
  125. }
  126. int ans = 0;
  127. int t[MAXN][MAXN][10];
  128. for(int i = 0; i < a; i++) {
  129. for(int j = 0; j < b; j++) {
  130. for(int k = 0; k < c; k++) {
  131. for(int st = 0; st < 10; st++) {
  132. t[k][j][st] = -INF;
  133. }
  134. }
  135. }
  136. for(int j = 0; j < b; j++) {
  137. for(int k = 0; k < c; k++) {
  138. if(m[i][j][k]) {
  139. d[j][k] = i;
  140. }
  141. t[k][j][0] = d[j][k];
  142. }
  143. }
  144. for(int j = 0; j < b; j++) {
  145. for(int k = 0; k < c; k++) {
  146. for(int st = 1; st < 10; st++) {
  147. if(j + (1 << st) < c) {
  148. t[k][j][st] = max(t[k][j][st - 1], t[k][j + (1 << (st - 1))][st - 1]);
  149. }
  150. }
  151. }
  152. }
  153. for(int j = 0; j < b; j++) {
  154. for(int k = j; k < b; k++) {
  155. vi tmp(c);
  156. for(int h = 0; h < c; h++) {
  157. int lg = log[k - j + 1];
  158. int mx = max(t[h][j][lg], t[h][k - lg + 1][lg]);
  159. tmp[h] = i - mx;
  160. cerr << i << " " << j << " " << k << " " << h << " " << mx << '\n';
  161. }
  162. stack<int> indl, indr;
  163. vi ml(c), mr(c);
  164. // cerr << i << " " << j << " " << k << " ";
  165. for(int h = 0; h < c; h++) {
  166. while(indl.size() && tmp[indl.top()] >= tmp[h]) {
  167. indl.pop();
  168. }
  169. ml[h] = ((!indl.size()) ? 0 : indl.top() + 1);
  170. indl.push(h);
  171. }
  172. for(int h = c - 1; h >= 0; h--) {
  173. while(indr.size() && tmp[indr.top()] >= tmp[h]) {
  174. indr.pop();
  175. }
  176. mr[h] = ((!indr.size()) ? c - 1 : indr.top() - 1);
  177. // cerr << "{" << ml[h] << ", " << mr[h] << "} ";
  178. indr.push(h);
  179. }
  180. // cerr << '\n';
  181. int res = 0;
  182. for(int h = 0; h < c; h++) {
  183. res = max(res, (mr[h] - ml[h] + 1) * tmp[h]);
  184. }
  185. ans = max(ans, res * (k - j + 1));
  186. }
  187. }
  188. }
  189. cout << ans;
  190. return 0;
  191. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement