oj.uz

Submission #959515

# Submission time Handle Problem Language Result Execution time Memory
959515 2024-04-08T11:23:15 Z NemanjaSo2005 Rectangles (IOI19_rect) C++17
13 / 100
 468 ms 233524 KB 
#include "rect.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2505;
ll res=0;
int N,M,mat[maxn][maxn],leftt[maxn][maxn],rightt[maxn][maxn],down[maxn][maxn],up[maxn][maxn],prefud[maxn][maxn],preflr[maxn][maxn];
bool checkmat(int i1,int j1,int i2,int j2){
   if(i1<=1 or j1<=1 or i2>=N or j2>=M)
      return false;
   if(i2<i1 or j2<j1)
      return false;

   /// Suma je 0
   for(int i=i1;i<=i2;i++)
      if(preflr[i][j2]-preflr[i][j1-1]!=0)
         return false;

   /// Okruzena 1
   if(preflr[i1-1][j2]-preflr[i1-1][j1-1]!=j2-j1+1)
      return false;
   if(preflr[i2+1][j2]-preflr[i2+1][j1-1]!=j2-j1+1)
      return false;
   if(prefud[i2][j1-1]-prefud[i1-1][j1-1]!=i2-i1+1)
      return false;
   if(prefud[i2][j2+1]-prefud[i1-1][j2+1]!=i2-i1+1)
      return false;
   return true;
}
bool checkgood(int x,int y){
   if(mat[x][y]==1)
      return false;
   int l=leftt[x][y]+1;
   int r=rightt[x][y]-1;
   int u=up[x][y]+1;
   int d=down[x][y]-1;

//   cout<<l<<" "<<r<<" "<<u<<" "<<d<<endl;

   if(l<=0 or r<=0 or u<=0 or d<=0)
      return false;

   return checkmat(u,l,d,r);
}
ll count_rectangles(std::vector<std::vector<int> > inp) {
	N=inp.size();
	M=inp[0].size();
   for(int i=1;i<=N;i++)
      for(int j=1;j<=M;j++){
         mat[i][j]=inp[i-1][j-1];
         prefud[i][j]=prefud[i-1][j]+mat[i][j];
         preflr[i][j]=preflr[i][j-1]+mat[i][j];
      }

   for(int i=1;i<=N;i++){
      for(int j=1;j<=M;j++){
         leftt[i][j]=leftt[i][j-1];
         if(mat[i][j]==1)
            leftt[i][j]=j;
      }
      for(int j=M;j>=1;j--){
         rightt[i][j]=rightt[i][j+1];
         if(mat[i][j]==1)
            rightt[i][j]=j;
      }
   }

   for(int j=1;j<=M;j++){
      for(int i=1;i<=N;i++){
         up[i][j]=up[i-1][j];
         if(mat[i][j]==1)
            up[i][j]=i;
      }
      for(int i=N;i>=1;i--){
         down[i][j]=down[i+1][j];
         if(mat[i][j]==1)
            down[i][j]=i;
      }
   }
   //cout<<checkgood(4,3)<<endl;
   //return 0;


   for(int i=2;i<N;i++)
      for(int j=2;j<M;j++){
         if(mat[i-1][j]!=1)
            continue;
         if(mat[i][j-1]!=1)
            continue;
         if(checkgood(i,j))
            res++;
      }

   return res;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 189 ms 113072 KB Output is correct
3 Correct 462 ms 232116 KB Output is correct
4 Correct 465 ms 233300 KB Output is correct
5 Correct 468 ms 233524 KB Output is correct
6 Correct 152 ms 115440 KB Output is correct
7 Correct 352 ms 229304 KB Output is correct
8 Correct 380 ms 233500 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 1116 KB Output is correct
12 Correct 1 ms 1116 KB Output is correct
13 Correct 1 ms 604 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -