Submission #411434

#	Time	Username	Problem	Language	Result	Execution time	Memory
411434		alextodoran	Quality Of Living (IOI10_quality)	C++17	100 / 100	2045 ms	155948 KiB

quality

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

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

using namespace std;

typedef long long ll;

const int NM_MAX = 3000;

int n, m;

int r, c;

int mat[NM_MAX + 2][NM_MAX + 2];

int sum[NM_MAX + 2][NM_MAX + 2];

bool solve (int lwr)
{
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            sum[i][j] = (mat[i][j] < lwr) + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
    for(int i = r; i <= n; i++)
        for(int j = c; j <= m; j++)
        {
            int in = sum[i][j] - sum[i - r][j] - sum[i][j - c] + sum[i - r][j - c];
            if(in <= r * c / 2)
                return true;
        }
    return false;
}

int rectangle (int N, int M, int R, int C, int Q[NM_MAX + 1][NM_MAX + 1])
{
    n = N;
    m = M;
    r = R;
    c = C;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            mat[i][j] = n * m - Q[i - 1][j - 1] + 1;
    int l = 1, r = n * m;
    while(l < r)
    {
        int mid = (l + r + 1) / 2;
        if(solve(mid) == true)
            l = mid;
        else
            r = mid - 1;
    }
    return n * m - l + 1;
}

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