Submission #960390

#	Time	Username	Problem	Language	Result	Execution time	Memory
960390		AkibAzmain	Rectangles (IOI19_rect)	C++17	37 / 100	869 ms	1048576 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

long long count_rectangles (std::vector<std::vector<int> > a) {
  ll n = a.size ();
  ll m = a[0].size ();
  vector < vector < vector < ll > > >
    ra (n, vector < vector < ll > > (m, vector < ll > (m))),
    ca (m, vector < vector < ll > > (n, vector < ll > (n)));
  for (ll k = 0; k < n; ++k)
    for (ll i = 0; i < m; ++i)
      {
        int mx = 0;
        for (ll j = i + 2; j < m; ++j)
          {
            mx = max (mx, a[k][j - 1]);
            if (mx < a[k][i] && mx < a[k][j]) ra[k][i + 1][j - 1] = 1;
          }
      }
  for (ll k = 0; k < m; ++k)
    for (ll i = 0; i < n; ++i)
      {
        int mx = 0;
        for (ll j = i + 2; j < n; ++j)
          {
            mx = max (mx, a[j - 1][k]);
            if (mx < a[i][k] && mx < a[j][k]) ca[k][i + 1][j - 1] = 1;
          }
      }
  for (ll i = 1; i < n; ++i)
    for (ll j = 0; j < m; ++j)
      for (ll k = 0; k < m; ++k)
        ra[i][j][k] += ra[i - 1][j][k];
  for (ll i = 1; i < m; ++i)
    for (ll j = 0; j < n; ++j)
      for (ll k = 0; k < n; ++k)
        ca[i][j][k] += ca[i - 1][j][k];
  auto alp = [&] (auto &x, int a, int b, int c, int d)
  {
    return (x[d][a][b] - (c ? x[c - 1][a][b] : 0)) == d - c + 1;
  };
  int c = 0;
  for (ll i1 = 0; i1 < n; ++i1)
    for (ll i2 = i1; i2 < n; ++i2)
      for (ll j1 = 0; j1 < m; ++j1)
        for (ll j2 = j1; j2 < m; ++j2)
          if (alp (ca, i1, i2, j1, j2) && alp (ra, j1, j2, i1, i2))
            ++c;
  return c;
}

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