fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAX_N = 2005;
  6.  
  7. int n, m, k, nRotate, mRotate;
  8. int arr[MAX_N][MAX_N];
  9. int radius[MAX_N][MAX_N];
  10. int prefixSumUnit[2 * MAX_N][2 * MAX_N];
  11. int prefixSumUnitTriangle[2 * MAX_N][2 * MAX_N];
  12. long long prefixSum[2 * MAX_N][2 * MAX_N],
  13.     prefixSumTriangle[2 * MAX_N][2 * MAX_N];
  14. long long answer[MAX_N][MAX_N];
  15.  
  16. pair<int, int> getPos(int x, int y) { return make_pair(x + y - 1, n - x + y); }
  17.  
  18. int getSumUnit(int u, int v, int x, int y) {
  19.     u = max(u, 1);
  20.     v = max(v, 1);
  21.     x = min(x, nRotate);
  22.     y = min(y, nRotate);
  23.     return prefixSumUnit[x][y] - prefixSumUnit[x][v - 1] -
  24.            prefixSumUnit[u - 1][y] + prefixSumUnit[u - 1][v - 1];
  25. }
  26.  
  27. long long getSum(int u, int v, int x, int y) {
  28.     u = max(u, 1);
  29.     v = max(v, 1);
  30.     x = min(x, nRotate);
  31.     y = min(y, nRotate);
  32.     return prefixSum[x][y] - prefixSum[x][v - 1] - prefixSum[u - 1][y] +
  33.            prefixSum[u - 1][v - 1];
  34. }
  35.  
  36. void calculateRadius() {
  37.     int row, col;
  38.     for (int i = 1; i <= n; i++) {
  39.         for (int j = 1; j <= m; j++) {
  40.             tie(row, col) = getPos(i, j);
  41.             prefixSumUnit[row][col] = arr[i][j];
  42.         }
  43.     }
  44.     nRotate = n + m - 1;
  45.     for (int i = 1; i <= nRotate; i++) {
  46.         for (int j = 1; j <= nRotate; j++) {
  47.             prefixSumUnit[i][j] =
  48.                 prefixSumUnit[i][j] + prefixSumUnit[i - 1][j] +
  49.                 prefixSumUnit[i][j - 1] - prefixSumUnit[i - 1][j - 1];
  50.         }
  51.     }
  52.     radius[1][1] = 0;
  53.     tie(row, col) = getPos(1, 1);
  54.     while (getSumUnit(row - radius[1][1], col - radius[1][1],
  55.                       row + radius[1][1], col + radius[1][1]) < k) {
  56.         radius[1][1]++;
  57.     }
  58.     for (int j = 2; j <= m; j++) {
  59.         radius[1][j] = radius[1][j - 1] + 1;
  60.         int &tmp = radius[1][j];
  61.         tie(row, col) = getPos(1, j);
  62.         while (tmp > 0 && getSumUnit(row - tmp + 1, col - tmp + 1,
  63.                                      row + tmp - 1, col + tmp - 1) >= k) {
  64.             tmp--;
  65.         }
  66.     }
  67.     for (int i = 2; i <= n; i++) {
  68.         for (int j = 1; j <= m; j++) {
  69.             radius[i][j] = radius[i - 1][j] + 1;
  70.             int &tmp = radius[i][j];
  71.             tie(row, col) = getPos(i, j);
  72.             while (tmp > 0 && getSumUnit(row - tmp + 1, col - tmp + 1,
  73.                                          row + tmp - 1, col + tmp - 1) >= k) {
  74.                 tmp--;
  75.             }
  76.         }
  77.     }
  78. }
  79.  
  80. long long getSumTriangleX(int u, int v, int x, int y) {
  81.     long long result = 0;
  82.     if (u < 1) {
  83.         int tmp = 1 - u;
  84.         u += tmp;
  85.         v += tmp;
  86.     }
  87.     if (y > nRotate) {
  88.         int tmp = y - nRotate;
  89.         x -= tmp;
  90.         y -= tmp;
  91.     }
  92.     if (v < 1) {
  93.         int tmp = 1 - v;
  94.         result += getSum(u, 1, u + tmp - 1, y);
  95.         u += tmp;
  96.         v += tmp;
  97.     }
  98.     if (x > nRotate) {
  99.         int tmp = x - nRotate;
  100.         result += getSum(u, y - tmp + 1, nRotate, y);
  101.         x -= tmp;
  102.         y -= tmp;
  103.     }
  104.     result += prefixSumTriangle[x][y] - prefixSumTriangle[u - 1][v - 1] -
  105.               getSum(1, v, u - 1, y);
  106.     return result;
  107. }
  108.  
  109. int getSumUnitTriangleX(int u, int v, int x, int y) {
  110.     int result = 0;
  111.     if (u < 1) {
  112.         int tmp = 1 - u;
  113.         u += tmp;
  114.         v += tmp;
  115.     }
  116.     if (y > nRotate) {
  117.         int tmp = y - nRotate;
  118.         x -= tmp;
  119.         y -= tmp;
  120.     }
  121.     if (v < 1) {
  122.         int tmp = 1 - v;
  123.         result += getSumUnit(u, 1, u + tmp - 1, y);
  124.         u += tmp;
  125.         v += tmp;
  126.     }
  127.     if (x > nRotate) {
  128.         int tmp = x - nRotate;
  129.         result += getSumUnit(u, y - tmp + 1, nRotate, y);
  130.         x -= tmp;
  131.         y -= tmp;
  132.     }
  133.     result += prefixSumUnitTriangle[x][y] -
  134.               prefixSumUnitTriangle[u - 1][v - 1] - getSumUnit(1, v, u - 1, y);
  135.     return result;
  136. }
  137.  
  138. void calculateAnswerX() {
  139.     int row, col;
  140.     for (int i = 1; i <= n; i++) {
  141.         for (int j = 1; j <= m; j++) {
  142.             tie(row, col) = getPos(i, j);
  143.             prefixSum[row][col] = i * arr[i][j];
  144.             prefixSumUnitTriangle[row][col] = arr[i][j];
  145.             prefixSumTriangle[row][col] = i * arr[i][j];
  146.         }
  147.     }
  148.     for (int i = 1; i <= nRotate; i++) {
  149.         for (int j = 1; j <= nRotate; j++) {
  150.             prefixSum[i][j] = prefixSum[i][j] + prefixSum[i - 1][j] +
  151.                               prefixSum[i][j - 1] - prefixSum[i - 1][j - 1];
  152.         }
  153.     }
  154.     for (int i = 2; i <= nRotate; i++) {
  155.         for (int j = 1; j <= nRotate; j++) {
  156.             prefixSumUnitTriangle[i][j] = prefixSumUnitTriangle[i][j] +
  157.                                           prefixSumUnitTriangle[i - 1][j] +
  158.                                           prefixSumUnitTriangle[i - 1][j - 1] -
  159.                                           prefixSumUnitTriangle[i - 2][j - 1];
  160.  
  161.             prefixSumTriangle[i][j] = prefixSumTriangle[i][j] +
  162.                                       prefixSumTriangle[i - 1][j] +
  163.                                       prefixSumTriangle[i - 1][j - 1] -
  164.                                       prefixSumTriangle[i - 2][j - 1];
  165.         }
  166.     }
  167.     for (int i = 1; i <= n; i++) {
  168.         for (int j = 1; j <= m; j++) {
  169.             if (radius[i][j] > 0) {
  170.                 tie(row, col) = getPos(i, j);
  171.                 int tmp = radius[i][j] - 1;
  172.                 int sumUnitUpTriangle = getSumUnitTriangleX(
  173.                     row - tmp, col - tmp, row + tmp, col + tmp);
  174.                 long long sumUpTriangle =
  175.                     getSumTriangleX(row - tmp, col - tmp, row + tmp, col + tmp);
  176.                 int sumUnitArea =
  177.                     getSumUnit(row - tmp, col - tmp, row + tmp, col + tmp);
  178.                 long long sumArea =
  179.                     getSum(row - tmp, col - tmp, row + tmp, col + tmp);
  180.                 answer[i][j] += i * sumUnitUpTriangle - sumUpTriangle +
  181.                                 (sumArea - sumUpTriangle) -
  182.                                 i * (sumUnitArea - sumUnitUpTriangle);
  183.             }
  184.         }
  185.     }
  186. }
  187.  
  188. long long getSumTriangleY(int u, int v, int x, int y) {
  189.     long long result = 0;
  190.     if (u < 1) {
  191.         int tmp = 1 - u;
  192.         u += tmp;
  193.         v -= tmp;
  194.     }
  195.     if (y < 1) {
  196.         int tmp = 1 - y;
  197.         x -= tmp;
  198.         y += tmp;
  199.     }
  200.     if (x > nRotate) {
  201.         int tmp = x - nRotate;
  202.         result += getSum(u, y, nRotate, y + tmp - 1);
  203.         x -= tmp;
  204.         y += tmp;
  205.     }
  206.     if (v > nRotate) {
  207.         int tmp = v - nRotate;
  208.         result += getSum(u, y, u + tmp - 1, nRotate);
  209.         u += tmp;
  210.         v -= tmp;
  211.     }
  212.     result += prefixSumTriangle[x][y] - prefixSumTriangle[u - 1][v + 1] -
  213.               getSum(1, y, u - 1, v);
  214.     return result;
  215. }
  216.  
  217. int getSumUnitTriangleY(int u, int v, int x, int y) {
  218.     int result = 0;
  219.     if (u < 1) {
  220.         int tmp = 1 - u;
  221.         u += tmp;
  222.         v -= tmp;
  223.     }
  224.     if (y < 1) {
  225.         int tmp = 1 - y;
  226.         x -= tmp;
  227.         y += tmp;
  228.     }
  229.     if (x > nRotate) {
  230.         int tmp = x - nRotate;
  231.         result += getSumUnit(u, y, nRotate, y + tmp - 1);
  232.         x -= tmp;
  233.         y += tmp;
  234.     }
  235.     if (v > nRotate) {
  236.         int tmp = v - nRotate;
  237.         result += getSumUnit(u, y, u + tmp - 1, nRotate);
  238.         u += tmp;
  239.         v -= tmp;
  240.     }
  241.     result += prefixSumUnitTriangle[x][y] -
  242.               prefixSumUnitTriangle[u - 1][v + 1] - getSumUnit(1, y, u - 1, v);
  243.     return result;
  244. }
  245.  
  246. void calculateAnswerY() {
  247.     memset(prefixSum, 0, sizeof(prefixSum));
  248.     memset(prefixSumTriangle, 0, sizeof(prefixSumTriangle));
  249.     memset(prefixSumUnitTriangle, 0, sizeof(prefixSumUnitTriangle));
  250.     int row, col;
  251.     for (int i = 1; i <= n; i++) {
  252.         for (int j = 1; j <= m; j++) {
  253.             tie(row, col) = getPos(i, j);
  254.             prefixSum[row][col] = j * arr[i][j];
  255.             prefixSumUnitTriangle[row][col] = arr[i][j];
  256.             prefixSumTriangle[row][col] = j * arr[i][j];
  257.         }
  258.     }
  259.     for (int i = 1; i <= nRotate; i++) {
  260.         for (int j = 1; j <= nRotate; j++) {
  261.             prefixSum[i][j] = prefixSum[i][j] + prefixSum[i - 1][j] +
  262.                               prefixSum[i][j - 1] - prefixSum[i - 1][j - 1];
  263.         }
  264.     }
  265.     for (int i = 2; i <= nRotate; i++) {
  266.         for (int j = 1; j <= nRotate; j++) {
  267.             prefixSumUnitTriangle[i][j] = prefixSumUnitTriangle[i][j] +
  268.                                           prefixSumUnitTriangle[i - 1][j] +
  269.                                           prefixSumUnitTriangle[i - 1][j + 1] -
  270.                                           prefixSumUnitTriangle[i - 2][j + 1];
  271.  
  272.             prefixSumTriangle[i][j] = prefixSumTriangle[i][j] +
  273.                                       prefixSumTriangle[i - 1][j] +
  274.                                       prefixSumTriangle[i - 1][j + 1] -
  275.                                       prefixSumTriangle[i - 2][j + 1];
  276.         }
  277.     }
  278.     for (int i = 1; i <= n; i++) {
  279.         for (int j = 1; j <= m; j++) {
  280.             if (radius[i][j] > 0) {
  281.                 tie(row, col) = getPos(i, j);
  282.                 int tmp = radius[i][j] - 1;
  283.                 int sumUnitUpTriangle = getSumUnitTriangleY(
  284.                     row - tmp, col + tmp, row + tmp, col - tmp);
  285.                 long long sumUpTriangle =
  286.                     getSumTriangleY(row - tmp, col + tmp, row + tmp, col - tmp);
  287.                 int sumUnitArea =
  288.                     getSumUnit(row - tmp, col - tmp, row + tmp, col + tmp);
  289.                 long long sumArea =
  290.                     getSum(row - tmp, col - tmp, row + tmp, col + tmp);
  291.                 answer[i][j] += j * sumUnitUpTriangle - sumUpTriangle +
  292.                                 (sumArea - sumUpTriangle) -
  293.                                 j * (sumUnitArea - sumUnitUpTriangle);
  294.             }
  295.         }
  296.     }
  297. }
  298.  
  299. long long calculateAnswer() {
  300.     long long result = 0;
  301.     int row, col;
  302.     for (int i = 1; i <= n; i++) {
  303.         for (int j = 1; j <= m; j++) {
  304.             if (radius[i][j] > 0) {
  305.                 tie(row, col) = getPos(i, j);
  306.                 int tmp = radius[i][j] - 1;
  307.                 result += answer[i][j] +
  308.                           radius[i][j] * (k - getSumUnit(row - tmp, col - tmp,
  309.                                                          row + tmp, col + tmp));
  310.             }
  311.         }
  312.     }
  313.     return result;
  314. }
  315.  
  316. int main() {
  317.     ios_base::sync_with_stdio(false);
  318.     cin.tie(0);
  319.     cout.tie(0);
  320.     freopen("formation.inp", "r", stdin);
  321.     freopen("formation.out", "w", stdout);
  322.     cin >> n >> m >> k;
  323.     for (int i = 1; i <= n; i++) {
  324.         for (int j = 1; j <= m; j++) {
  325.             cin >> arr[i][j];
  326.         }
  327.     }
  328.     calculateRadius();
  329.     calculateAnswerX();
  330.     calculateAnswerY();
  331.     cout << calculateAnswer();
  332.     return 0;
  333. }
  334.  
Success #stdin #stdout 0.05s 320580KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/x3MnpD
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!