Submission #407441

#	Time	Username	Problem	Language	Result	Execution time	Memory
407441		soba	Quality Of Living (IOI10_quality)	C++14	100 / 100	3110 ms	140216 KiB

quality

#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int l=1 , r= 3000*3000 , m , ans=r ;
	int arr[R+1][C+1]={0};
	int x;
	bool flag;
	while(l<=r)
    {
        m=(l+r)>>1;
        memset(arr , 0 , sizeof arr);
        for(int i = 0 ; i  < R ;  i++)
        {
            for(int j = 0 ; j < C ;j++)
            {
                if(Q[i][j]<=m)
                {
                    arr[i+1][j+1]=1;
                }
            }
        }
        for(int i = 1 ; i <= R ; i++)
        {
            for(int j = 1 ; j <=C ; j++)
            {
                arr[i][j]+= arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1];
            }
        }
//        for(int i = 1 ; i <= R ; i++)
//        {
//            for(int j = 1 ; j <=C ; j++)
//            {
//                arr[i][j]+=arr[i-1][j];
//            }
//        }
        flag=false;
      //  cout << "checking mid = " << m << ":-\n";
        for(int i = H ; i <=R ; i++)
        {
            for(int j = W ; j<=C ; j++)
            {
                //cout << "in " << i << " " << j << " = " ;
                x=arr[i][j]+arr[i-H][j-W]-arr[i-H][j]-arr[i][j-W];
                //cout << x << "\n";
                if(x>=(H*W)-x)
                {
                    flag=true;
                    break;
                }
            }
            if(flag)
                break;
        }
        if(flag)
        {
            ans=m;
            r=m-1;
        }
        else
        {
            l=m+1;
        }
    }
    return ans;

}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20