Submission #919672

#	Time	Username	Problem	Language	Result	Execution time	Memory
919672		boris_mihov	Quality Of Living (IOI10_quality)	C++17	100 / 100	1403 ms	176036 KiB

quality

#include "quality.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 3000 + 10;
const int INF  = 1e9;

int n, m;
int r, c;
int a[MAXN][MAXN];
int p[MAXN][MAXN];

bool check(int to)
{
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= m ; ++j)
        {
            p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + (a[i][j] <= to);
        }
    }

    for (int i = r ; i <= n ; ++i)
    {
        for (int j = c ; j <= m ; ++j)
        {
            int res = p[i][j];
            res -= p[i - r][j];
            res -= p[i][j - c];
            res += p[i - r][j - c];
            if (res > r * c / 2) return true;
        }
    }

    return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) 
{
    n = R; m = C; r = H; c = W;
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= m ; ++j)
        {
            a[i][j] = Q[i - 1][j - 1];
        }
    }

	int l = 0, r = n * m + 1, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (!check(mid)) l = mid;
        else r = mid;
    }

    return r;
}

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