Submission #542292

#	Time	Username	Problem	Language	Result	Execution time	Memory
542292		Trisanu_Das	Quality Of Living (IOI10_quality)	C++17	100 / 100	2331 ms	210692 KiB

quality

#include "grader.h"
#include <bits/stdc++.h>

using namespace std;

int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
    int smaller[R+1][C+1] , bigger[R+1][C+1] , arr[R+1][C+1];
    //make grid 1-indexed
    memset(smaller , 0 , sizeof(smaller)) ;
    memset(bigger , 0 , sizeof(bigger)) ;
    for(int i = 1 ; i <= R ; ++i)
    {
        for(int j = 1 ; j <= C ; ++j)
            arr[i][j] = Q[i-1][j-1] ;
    }
    int l = 1 , r = R*C , ans = R*C ;
    while(l <= r)
    {
        int mid = (l + r) / 2 ;
        for(int i = 1 ; i <= R ; ++i)
        {
            int s = 0 , b = 0 ;
            for(int j = 1 ; j <= C ; ++j)
            {
                smaller[i][j] = s + smaller[i-1][j];
                if(arr[i][j] < mid)
                    smaller[i][j]++ , ++s;
                bigger[i][j] = b + bigger[i-1][j] ;
                if(arr[i][j] > mid)
                    bigger[i][j]++ , ++b;
            }
        }
        bool t = false ;
        for(int i = 1 ; i <= R-H+1 ; ++i)
        {
            for(int j = 1 ; j <= C-W+1 ; ++j)
            {
                int s = smaller[i+H-1][j+W-1] - smaller[i+H-1][j-1] - smaller[i-1][j+W-1] + smaller[i-1][j-1] ;
                int b = bigger[i+H-1][j+W-1] - bigger[i+H-1][j-1] - bigger[i-1][j+W-1] + bigger[i-1][j-1] ;
                if(s >= b)
                    t = true ;
                int n = R*C ;
                if(s == b && s <= n/2 && b <= n/2)
                    ans = min(ans , mid) ;
            }
        }
        if(t == true)
            r = mid-1 ;
        else
            l = mid+1 ;
    }
    return ans ;
}

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