Submission #222285

#	Time	Username	Problem	Language	Result	Execution time	Memory
222285		mathking1021	Quality Of Living (IOI10_quality)	C++14	100 / 100	3012 ms	246372 KiB

quality

#include "quality.h"

typedef long long ll;

ll r, c, h, w;
ll a[3005][3005];
ll b[3005][3005];

bool f(ll p)
{
    for(ll i = 1; i <= r; i++)
    {
        for(ll j = 1; j <= c; j++)
        {
            if(a[i][j] <= p) b[i][j] = 1;
            else b[i][j] = 0;
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
        }
    }
    for(ll i = h; i <= r; i++)
    {
        for(ll j = w; j <= c; j++)
        {
            ll t = b[i][j] - b[i - h][j] - b[i][j - w] + b[i - h][j - w];
            if(t >= (h * w + 1) / 2) return true;
        }
    }
    return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    r = R;
    c = C;
    h = H;
    w = W;
    for(ll i = 0; i < r; i++)
    {
        for(ll j = 0; j < c; j++)
        {
            a[i + 1][j + 1] = Q[i][j];
        }
    }
    ll lt = 0, rt = r * c, mid, ans = 0;
    while(lt <= rt)
    {
        mid = (lt + rt) / 2;
        if(f(mid)) ans = mid, rt = mid - 1;
        else lt = mid + 1;
    }
    return ans;
}

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