Submission #1225952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225952		zNatsumi	Rectangles (IOI19_rect)	C++20	25 / 100	5096 ms	34888 KiB

rect

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 2500 + 5;

int n, m, a[N][N];

namespace sub1{
  ll solve(){
    ll res = 0LL;
    for(int r1 = 2; r1 < n; r1++)
      for(int r2 = r1; r2 < n; r2++)
        for(int c1 = 2; c1 < m; c1++)
          for(int c2 = c1; c2 < m; c2++){
            bool ok = true;
            for(int i = r1; i <= r2; i++)
              for(int j = c1; j <= c2; j++)
                if(a[i][j] >= min({a[i][c1 - 1], a[i][c2 + 1], a[r1 - 1][j], a[r2 + 1][j]})){
                  ok = false;
                  break;
                }
            res += ok;
          }
    return res;
  }
}

long long count_rectangles(vector<vector<int>> A){
  n = A.size(); m = A[0].size();
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++) a[i][j] = A[i - 1][j - 1];

  return sub1::solve();
}

//#define zNatsumi
#ifdef zNatsumi

int32_t main(){
  freopen("test.inp", "r", stdin);
  freopen("test.out", "w", stdout);

  int n, m; cin >> n >> m;
  vector<vector<int>> a(n, vector<int>(m, 0));
  for(int i = 0; i < n; i++)
    for(int j = 0; j < m; j++) cin >> a[i][j];
  cout << count_rectangles(a);
}

#endif

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