Submission #155181

#	Time	Username	Problem	Language	Result	Execution time	Memory
155181		flashmt	Rectangles (IOI19_rect)	C++17	13 / 100	265 ms	111024 KiB

rect

#include <bits/stdc++.h>
using namespace std;
const int N = 2525;

int m, n, maxRow[N][N], maxCol[N][N], sum[N][N];
vector<vector<int>> a;

long long subtask5()
{
  return 0;
}

int getSum(int x, int y, int xx, int yy)
{
  return sum[xx][yy] + sum[x][y] - sum[xx][y] - sum[x][yy];
}

long long subtask6()
{
  for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
      sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i - 1][j - 1];

  vector<int> maxCol(n + 1, 0);
  long long ans = 0;
  for (int i = 2; i < m; i++)
  {
    int maxRow = 0;
    for (int j = 2; j < n; j++)
      if (!a[i - 1][j - 1])
      {
        maxRow++;
        maxCol[j]++;
        int ii = i - maxCol[j] + 1, jj = j - maxRow + 1;
        ans += getSum(ii - 1, jj - 1, i, j) == 0 &&
               getSum(ii - 2, jj - 1, ii - 1, j) == maxRow &&
               getSum(i, jj - 1, i + 1, j) == maxRow &&
               getSum(ii - 1, jj - 2, i, jj - 1) == maxCol[j] &&
               getSum(ii - 1, j, i, j + 1) == maxCol[j];
      }
      else maxRow = maxCol[j] = 0;
  }

  return ans;
}

long long count_rectangles(vector<vector<int>> _a)
{
  a = _a;
  m = a.size();
  n = a[0].size();

  // if (m == 3)
  //   return subtask5();

  for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
      if (a[i][j] > 1)
        return 0;

  return subtask6();
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28