Submission #891480

#	Time	Username	Problem	Language	Result	Execution time	Memory
891480		Faisal_Saqib	Rectangles (IOI19_rect)	C++17	37 / 100	3326 ms	1048576 KiB

rect

#include <vector>
#include <iostream>
using namespace std;
long long count_rectangles(std::vector<std::vector<int> >a)
{
	long long ans=0;
	int n=a.size();
	int m=a[0].size();
	int fix1[n][m][m];
	for(int i=1;i<=(n-2);i++)
	{
		for(int j=1;j<=(m-2);j++)
		{
			fix1[i][j][j]=a[i][j];
			int j1=j+1;
			while(j1<=(m-2))
			{
				fix1[i][j][j1]=max(a[i][j1],fix1[i][j][j1-1]);
				j1++;
			}
		}
	}
	int fix2[m][n][n];
	for(int i=1;i<=(m-2);i++)
	{
		for(int j=1;j<=(n-2);j++)
		{
			fix2[i][j][j]=a[j][i];
			int j1=j+1;
			while(j1<=(n-2))
			{
				fix2[i][j][j1]=max(a[j1][i],fix2[i][j][j1-1]);
				j1++;
			}
		}
	}
	for(int r1=1;r1<=(n-2);r1++)
	{
		for(int c1=1;c1<=(m-2);c1++)
		{
			for(int r2=r1;r2<=(n-2);r2++)
			{
				for(int c2=c1;c2<=(m-2);c2++)
				{
					bool pos=1;
					for(int addi=0;addi<=(r2-r1) and pos;addi++)
					{
						int celli=r1+addi;
						int mi=min(a[celli][c1-1],a[celli][c2+1]);
						int fp=fix1[celli][c1][c2];
						if(fp>=mi)
						{
							// if(r1==1 and c1==1 and r2==2 and c2==1)
							// {
							// 	cout<<"Hell "<<mi<<endl;
							// 	cout<<fp<<endl;
							// 	cout<<celli<<endl;
							// }
							pos=0;
							break;
						}
					}
					for(int addj=0;addj<=(c2-c1);addj++)
					{
						int cellj=c1+addj;
						int mi=min(a[r1-1][cellj],a[r2+1][cellj]);
						int fp=fix2[cellj][r1][r2];
						if(fp>=mi)
						{
							// if(r1==1 and c1==1 and r2==2 and c2==1)
							// {
							// 	cout<<"Hell "<<mi<<endl;
							// 	cout<<fp<<endl;
							// }
							pos=0;
							break;
						}
					}
					// if(pos)
					// {
					// 	cout<<"Hello "<<r1<<' '<<c1<<' '<<r2<<' '<<c2<<' '<<pos<<endl;
					// }
					ans+=pos;
				}
			}
		}
	}
	return ans;
}

• 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