Submission #262226

#	Time	Username	Problem	Language	Result	Execution time	Memory
262226		Alexa2001	Quality Of Living (IOI10_quality)	C++17	100 / 100	2423 ms	140628 KiB

quality

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

using namespace std;

int n, m, r, c, s[3001][3001];

bool check(int val, int a[3001][3001])
{
    int i, j;

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
        {
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + (a[i-1][j-1] <= val ? 1 : -1);

            if(i >= r && j >= c)
                if(s[i][j] - s[i-r][j] - s[i][j-c] + s[i-r][j-c] >= 0)
                    return 1;
        }
    return 0;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
    int st, dr, mid;
    st = 1; dr = R * C;
    n = R; m = C;
    r = H; c = W;

    while(st <= dr)
    {
        mid = (st + dr) / 2;
        if(check(mid, Q)) dr = mid - 1;
            else st = mid + 1;
    }

    return st;
}

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