Submission #959524

#	Time	Username	Problem	Language	Result	Execution time	Memory
959524		NemanjaSo2005	Rectangles (IOI19_rect)	C++17	37 / 100	5052 ms	40844 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],maks[maxn];
bool moze[maxn];
ll prebroj(int x,int y){
   ll ret=0;
   for(int j=y;j<M;j++){
      moze[j]=true;
      maks[j]=mat[x][j];
   }

   for(int i=x;i<N;i++){
      int rmaks=0;
      for(int j=y;j<M;j++){
         rmaks=max(rmaks,mat[i][j]);
         moze[j]&=(rmaks<mat[i][y-1] and  rmaks<mat[i][j+1]);
      }
      for(int j=y;j<M;j++)
         maks[j]=max(maks[j],mat[i][j]);
      for(int j=y;j<M;j++){
         if(maks[j]>=mat[i+1][j])
            break;
         if(maks[j]>=mat[x-1][j])
            break;
         if(!moze[j])
            continue;
         ret++;
        //cout<<x<<" "<<y<<" "<<i<<" "<<j<<endl;
      }
   }
   return ret;
}
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];

   for(int i=2;i<N;i++)
      for(int j=2;j<M;j++)
         res+=prebroj(i,j);
   return res;
}

• 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