Submission #959515

#	Time	Username	Problem	Language	Result	Execution time	Memory
959515		NemanjaSo2005	Rectangles (IOI19_rect)	C++17	13 / 100	468 ms	233524 KiB

rect

#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
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28