API tools faq
paste
Advertisement
Guest User

Моя H

a guest
Mar 23rd, 2018
89
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 12.66 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1515;
  6. const int M = 1515;
  7.  
  8. int n;
  9. int m;
  10. int k;
  11.  
  12. int ps[N][M];
  13. int ma3x[N][M];
  14.  
  15. int angle[4][N][M];
  16. int vertical[2][M];
  17. int horizontal[2][N];
  18.  
  19. void read() {
  20.   scanf("%d %d %d", &n, &m, &k);
  21.   for (int i = 1; i <= n; i++) {
  22.     for (int j = 1; j <= m; j++) {
  23.       scanf("%d", &ma3x[i][j]);
  24.     }
  25.   }
  26. }
  27.  
  28. int getSum(int i1, int j1, int i2, int j2) {
  29.   return ps[i2][j2] - ps[i2][j1 - 1] - ps[i1 - 1][j2] + ps[i1 - 1][j1 - 1];
  30. }
  31.  
  32. void precompute() {
  33.   /// PS
  34.   for (int i = 1; i <= n; i++) {
  35.     for (int j = 1; j <= m; j++) {
  36.       ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + ma3x[i][j];
  37.     }
  38.   }
  39.   memset(angle, -1, sizeof(angle));
  40.   memset(vertical, -1, sizeof(vertical));
  41.   memset(horizontal, -1, sizeof(horizontal));
  42.   /// ANGLE (One square)
  43.   for (int i = 1; i <= n; i++) {
  44.     for (int j = 1; j <= m; j++) {
  45.       if (i >= k && j >= k) {
  46.         angle[0][i][j] = getSum(i - k + 1, j - k + 1, i, j);
  47.         angle[0][i][j] = max(angle[0][i][j], angle[0][i - 1][j]);
  48.         angle[0][i][j] = max(angle[0][i][j], angle[0][i][j - 1]);
  49.       }
  50.     }
  51.   }
  52.   for (int i = 1; i <= n; i++) {
  53.     for (int j = m; j >= 1; j--) {
  54.       if (i >= k && j + k - 1 <= m) {
  55.         angle[2][i][j] = getSum(i - k + 1, j, i, j + k - 1);
  56.         angle[2][i][j] = max(angle[2][i][j], angle[2][i - 1][j]);
  57.         angle[2][i][j] = max(angle[2][i][j], angle[2][i][j + 1]);
  58.       }
  59.     }
  60.   }
  61.   for (int i = n; i >= 1; i--) {
  62.     for (int j = 1; j <= m; j++) {
  63.       if (i + k - 1 <= n && j >= k) {
  64.         angle[1][i][j] = getSum(i, j - k + 1, i + k - 1, j);
  65.         angle[1][i][j] = max(angle[1][i][j], angle[1][i + 1][j]);
  66.         angle[1][i][j] = max(angle[1][i][j], angle[1][i][j - 1]);
  67.       }
  68.     }
  69.   }
  70.   for (int i = n; i >= 1; i--) {
  71.     for (int j = m; j >= 1; j--) {
  72.       if (i + k - 1 <= n && j + k - 1 <= m) {
  73.         angle[3][i][j] = getSum(i, j, i + k - 1, j + k - 1);
  74.         angle[3][i][j] = max(angle[3][i][j], angle[3][i + 1][j]);
  75.         angle[3][i][j] = max(angle[3][i][j], angle[3][i][j + 1]);
  76.       }
  77.     }
  78.   }
  79.   /**
  80.     02
  81.     13
  82.     angle[i] = best subrectangle containing corner i
  83.   */   
  84.   /// VERTICAL (Two squares)
  85.   for (int j = k; j <= m; j++) {
  86.     vertical[0][j] = vertical[0][j - 1];
  87.     for (int i = 1; i + k - 1 <= n; i++) {
  88.       int fixed = getSum(i, j - k + 1, i + k - 1, j);
  89.       int val1 = -1, val2 = -1, val3 = -1;
  90.       if (angle[0][i - 1][j] != -1) {
  91.         val1 = fixed + angle[0][i - 1][j];
  92.         /**      j
  93.         0------------2
  94.         |        |   |
  95.         |_______O|   |
  96.         |     XXX|   |
  97.         |     XXX|   | i
  98.         |     XXX|   |
  99.         |        |   |
  100.         |        |   |
  101.         1------------3
  102.         */
  103.       }
  104.       if (angle[1][i + k][j] != -1) {
  105.         val2 = fixed + angle[1][i + k][j];
  106.         /**      j
  107.         0------------2
  108.         |        |   |
  109.         |        |   |
  110.         |     XXX|   |
  111.         |     XXX|   | i
  112.         |     XXX|   |
  113.         |--------|   |
  114.         |       O|   |
  115.         |        |   |
  116.         1------------3
  117.         */
  118.       }
  119.       if (angle[0][n][j - k] != -1) {
  120.         val3 = fixed + angle[0][n][j - k];
  121.         /**      j
  122.         0------------2
  123.         |    |   |   |
  124.         |    |   |   |
  125.         |    |XXX|   |
  126.         |    |XXX|   | i
  127.         |    |XXX|   |
  128.         |    |   |   |
  129.         |   O|   |   |
  130.         1------------3
  131.         */
  132.       }
  133.       vertical[0][j] = max(max(vertical[0][j], val1), max(val2, val3));
  134.     }
  135.   }
  136.   for (int j = m - k + 1; j >= 1; j--) {
  137.     vertical[1][j] = vertical[1][j + 1];
  138.     for (int i = 1; i + k - 1 <= n; i++) {
  139.       int fixed = getSum(i, j, i + k - 1, j + k - 1);
  140.       int val1 = -1, val2 = -1, val3 = -1;
  141.       if (angle[3][1][j + k] != -1) {
  142.         val1 = fixed + angle[3][1][j + k];
  143.         /**      j
  144.         0----------------------------2
  145.         |        |   |O              |
  146.         |        |   |               |
  147.       i |        |XXX|               |
  148.         |        |XXX|               |
  149.         |        |XXX|               |
  150.         |        |   |               |
  151.         |        |   |               |
  152.         1----------------------------3
  153.         */
  154.       }
  155.       if (angle[2][i - 1][j] != -1) {
  156.         val2 = fixed + angle[2][i - 1][j];
  157.         /**      j
  158.         0----------------------------2
  159.         |        |                   |
  160.         |        |O__________________|
  161.       i |        |XXX                |
  162.         |        |XXX                |
  163.         |        |XXX                |
  164.         |        |                   |
  165.         |        |                   |
  166.         1----------------------------3
  167.         */
  168.       }
  169.       if (angle[3][i + k][j] != -1) {
  170.         val3 = fixed + angle[3][i + k][j];
  171.         /**      j
  172.         0----------------------------2
  173.         |        |                   |
  174.         |        |                   |
  175.       i |        |XXX                |
  176.         |        |XXX                |
  177.         |        |XXX                |
  178.         |        |O__________________|
  179.         |        |                   |
  180.         1----------------------------3
  181.         */
  182.       }
  183.       vertical[1][j] = max(max(vertical[1][j], val1), max(val2, val3));
  184.     }
  185.   }
  186.   /// HORIZONTAL (Two squares)
  187.   for (int i = k; i <= n; i++) {
  188.     horizontal[0][i] = horizontal[0][i - 1];
  189.     for (int j = 1; j + k - 1 <= m; j++) {
  190.       int fixed = getSum(i - k + 1, j, i, j + k - 1);
  191.       int val1 = -1, val2 = -1, val3 = -1;
  192.       if (angle[0][i][j - 1] != -1) {
  193.         val1 = fixed + angle[0][i][j - 1];
  194.         /**      j            
  195.         0----------------------------2
  196.         |       |                    |
  197.         |       |                    |        
  198.         |       |                    |        
  199.         |       |XXX                 |
  200.         |       |XXX                 |
  201.       i |_______OXXX_________________|
  202.         |                            |
  203.         |                            |
  204.         |                            |
  205.         |                            |
  206.         1----------------------------3
  207.         */
  208.       }
  209.       if (angle[2][i][j + k] != -1) {
  210.         val2 = fixed + angle[2][i][j + k];
  211.         /**      j            
  212.         0----------------------------2
  213.         |           |                |
  214.         |           |                |        
  215.         |           |                |        
  216.         |        XXX|                |
  217.         |        XXX|                |
  218.       i |________XXXO________________|
  219.         |                            |
  220.         |                            |
  221.         |                            |
  222.         |                            |
  223.         1----------------------------3
  224.         */
  225.       }
  226.       if (angle[2][i - k][1] != -1) {
  227.         val3 = fixed + angle[2][i - k][1];
  228.         /**      j            
  229.         0----------------------------2
  230.         |                            |
  231.         |                            |        
  232.         |O___________________________|        
  233.         |        XXX                 |
  234.         |        XXX                 |
  235.       i |________XXX_________________|
  236.         |                            |
  237.         |                            |
  238.         |                            |
  239.         |                            |
  240.         1----------------------------3
  241.         */
  242.       }
  243.       horizontal[0][i] = max(max(horizontal[0][i], val1), max(val2, val3));
  244.     }
  245.   }
  246.   for (int i = n - k + 1; i >= 1; i--) {
  247.     horizontal[1][i] = horizontal[1][i + 1];
  248.     for (int j = 1; j + k - 1 <= m; j++) {
  249.       int fixed = getSum(i, j, i + k - 1, j + k - 1);
  250.       int val1 = -1, val2 = -1, val3 = -1;
  251.       if (angle[1][i][j - 1] != -1) {
  252.         val1 = fixed + angle[1][i][j - 1];
  253.         /**      j
  254.         0----------------------------2
  255.         |                            |
  256.         |                            |        
  257.         |                            |
  258.       i |____________________________|
  259.         |       OXXX                 |
  260.         |       |XXX                 |
  261.         |       |XXX                 |
  262.         |       |                    |
  263.         |       |                    |
  264.         |       |                    |
  265.         |       |                    |
  266.         1----------------------------3
  267.         */
  268.       }
  269.       if (angle[3][i][j + k] != -1) {
  270.         val2 = fixed + angle[3][i][j + k];
  271.         /**      j
  272.         0----------------------------2
  273.         |                            |
  274.         |                            |        
  275.         |                            |
  276.       i |____________________________|
  277.         |        XXXO                |
  278.         |        XXX|                |
  279.         |        XXX|                |
  280.         |           |                |
  281.         |           |                |
  282.         |           |                |
  283.         |           |                |
  284.         1----------------------------3
  285.         */
  286.       }
  287.       if (angle[3][i + k][1] != -1) {
  288.         val3 = fixed + angle[3][i + k][1];
  289.         /**      j
  290.         0----------------------------2
  291.         |                            |
  292.         |                            |        
  293.         |                            |
  294.       i |____________________________|
  295.         |        XXX                 |
  296.         |        XXX                 |
  297.         |        XXX                 |
  298.         |____________________________|
  299.         |O                           |
  300.         |                            |
  301.         |                            |
  302.         1----------------------------3
  303.         */
  304.       }
  305.       horizontal[1][i] = max(max(horizontal[1][i], val1), max(val2, val3));
  306.     }
  307.   }
  308. }
  309.  
  310. void solve() {
  311.   int ans = -1;
  312.   for (int i = 1; i + k - 1 <= n; i++) {
  313.     for (int j = 1; j + k - 1 <= m; j++) {
  314.       int fixed = getSum(i, j, i + k - 1, j + k - 1);
  315.       int val1 = -1, val2 = -1, val3 = -1, val4 = -1;          
  316.       if (horizontal[0][i - 1] != -1) {
  317.         val1 = fixed + horizontal[0][i - 1];
  318.         /**      j
  319.         0----------------------------2
  320.         |                            |
  321.         |                            |        
  322.         |                            |
  323.       i |____________________________|
  324.         |        XXX                 |
  325.         |        XXX                 |
  326.         |        XXX                 |
  327.         |                            |
  328.         |                            |
  329.         |                            |
  330.         |                            |
  331.         1----------------------------3
  332.         */
  333.       }
  334.       if (horizontal[1][i + k] != -1) {
  335.         val2 = fixed + horizontal[1][i + k];
  336.         /**      j
  337.         0----------------------------2
  338.         |                            |
  339.         |                            |        
  340.         |                            |
  341.       i |                            |
  342.         |        XXX                 |
  343.         |        XXX                 |
  344.         |        XXX                 |
  345.         |____________________________|
  346.         |                            |
  347.         |                            |
  348.         |                            |
  349.         1----------------------------3
  350.         */
  351.       }
  352.       if (vertical[0][j - 1] != -1) {
  353.         val3 = fixed + vertical[0][j - 1];
  354.         /**      j
  355.         0----------------------------2
  356.         |       |                    |
  357.         |       |                    |        
  358.         |       |                    |
  359.       i |       |                    |
  360.         |       |XXX                 |
  361.         |       |XXX                 |
  362.         |       |XXX                 |
  363.         |       |                    |
  364.         |       |                    |
  365.         |       |                    |
  366.         |       |                    |
  367.         1----------------------------3
  368.         */
  369.       }
  370.       if (vertical[1][j + k] != -1) {
  371.         val4 = fixed + vertical[1][j + k];
  372.         /**      j
  373.         0----------------------------2
  374.         |           |                |
  375.         |           |                |        
  376.         |           |                |
  377.       i |           |                |
  378.         |        XXX|                |
  379.         |        XXX|                |
  380.         |        XXX|                |
  381.         |           |                |
  382.         |           |                |
  383.         |           |                |
  384.         |           |                |
  385.         1----------------------------3
  386.         */
  387.       }
  388.       int tmp = max(max(val1, val2), max(val3, val4));
  389.       ans = max(ans, tmp);
  390.     }
  391.   }
  392.     cout << ans << "\n";
  393. }
  394.  
  395. int main() {
  396.   read();
  397.   precompute();
  398.   solve();
  399.   return 0;
  400. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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!