Submission #1034554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034554		lucri	Quality Of Living (IOI10_quality)	C++17	100 / 100	1549 ms	140392 KiB

quality

#include <bits/stdc++.h>
#include "quality.h"
int sum[3010][3010];
bool ok(int n,int m,int l,int c,int a[3001][3001],int val)
{
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(a[i-1][j-1]<=val)
                sum[i][j]=1+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
            else
                sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
    for(int i=l;i<=n;++i)
        for(int j=c;j<=m;++j)
            if(sum[i][j]-sum[i-l][j]-sum[i][j-c]+sum[i-l][j-c]>l*c/2)
                return true;
    return false;
}
int rectangle(int n,int m,int l,int c,int a[3001][3001])
{
    long long b=1,e=n*m;
    while(b<=e)
    {
        if(ok(n,m,l,c,a,(b+e)/2))
            e=(b+e)/2-1;
        else
            b=(b+e)/2+1;
    }
    return b;
}

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