Advertisement
Guest User

Untitled

a guest
Nov 19th, 2019
131
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.58 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5. #include <queue>
  6. #include <algorithm>
  7. #include <string>
  8. #include <cmath>
  9. #include <cstdio>
  10. #include <iomanip>
  11. #include <fstream>
  12. #include <cassert>
  13. #include <cstring>
  14. #include <unordered_set>
  15. #include <unordered_map>
  16. #include <numeric>
  17. #include <ctime>
  18. #include <bitset>
  19. #include <complex>
  20.  
  21. using namespace std;
  22.  
  23. struct Solver {
  24. int n, m;
  25. vector<vector<int>> a;
  26. vector<vector<vector<int>>> dp;
  27. vector<vector<vector<pair<int, int>>>> wr;
  28.  
  29. bool can_afford(int i, int l, int r) {
  30. for (int j = l; j <= r; j++) {
  31. if (a[i][j] == 0) {
  32. return false;
  33. }
  34. }
  35. return true;
  36. }
  37.  
  38. void calc() {
  39. dp.resize(n, vector<vector<int>> (m, vector<int> (m)));
  40. wr.resize(n, vector<vector<pair<int, int>>> (m, vector<pair<int, int>> (m, {-1, -1})));
  41. for (int i = 0; i < n; i++) {
  42. for (int l = 0; l < m; l++) {
  43. for (int r = l; r < m; r++) {
  44. if (!can_afford(i, l, r)) {
  45. continue;
  46. }
  47. if (i == 0) {
  48. dp[i][l][r] = r - l + 1;
  49. continue;
  50. }
  51. for (int sl = l; sl <= r; sl++) {
  52. for (int sr = sl; sr <= r; sr++) {
  53. dp[i][l][r] = max(dp[i][l][r], dp[i - 1][sl][sr]);
  54. }
  55. }
  56. dp[i][l][r] += (r - l + 1);
  57. }
  58. }
  59. }
  60. }
  61.  
  62. void init(vector<vector<int>> &a_) {
  63. a = a_;
  64. n = (int)a.size();
  65. m = (int)a[0].size();
  66. dp.clear();
  67. calc();
  68. }
  69. }
  70.  
  71. signed main() {
  72. ios_base::sync_with_stdio(false);
  73. cin.tie(0);
  74.  
  75. int n, m;
  76. cin >> n >> m;
  77. int st = 0;
  78. vector<vector<int>> a(n, vector<int> (m));
  79. for (int i = 0; i < n; i++) {
  80. for (int j = 0; j < m; j++) {
  81. char c;
  82. cin >> c;
  83. a[i][j] = (c == '1');
  84. st += a[i][j];
  85. }
  86. }
  87. Solver::init(a);
  88. auto up = Solver::dp;
  89. reverse(a.begin(), a.end());
  90. Solver::init(a);
  91. auto dw = Solver::dp;
  92. reverse(dw.begin(), dw.end());
  93. int ans = 0;
  94. for (int i = 0; i < n; i++) {
  95. for (int l = 0; l < m; l++) {
  96. for (int r = l; r < m; r++) {
  97. ans = max(ans, up[i][l][r] + dw[i][l][r] - (r - l + 1));
  98. }
  99. }
  100. }
  101. cout << ans << endl;
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement