oj.uz

Submission #871370

# Submission time Handle Problem Language Result Execution time Memory
871370 2023-11-10T16:33:07 Z honanhphong Quality Of Living (IOI10_quality) C++14
100 / 100
 2457 ms 251860 KB 
#include <bits/stdc++.h>
using namespace std;
using lli = long long;
using ld = long double;
using pii = pair <int, int>;
const int maxn = 3e3 + 1000;
const int mod = 1e9 + 7;
int m, n, h, w, b[maxn][maxn], a[maxn][maxn], pre[maxn][maxn], q[3001][3001];

bool check(lli x)
{
    for (lli i = 1; i <= m; i ++)
    {
        for (lli j = 1; j <= n; j ++)
        {
            a[i][j] = 0;
        }
    }
    for (lli i = 1; i <= m; i ++)
    {
        for (lli j = 1; j <= n; j ++)
        {
            if (b[i][j] <= x)
            {
                a[i][j] = 1;
            }
        }
    }
    for (lli i = 1; i <= m; i ++)
    {
        for (lli j = 1; j <= n; j ++)
        {
            pre[i][j] = a[i][j] + pre[i][j - 1] + pre[i - 1][j] - pre[i - 1][j - 1];
        }
    }
    for (lli i = 1; i <= m - h + 1; i ++)
    {
        for (lli j = 1; j <= n - w + 1; j ++)
        {
            lli sum = pre[i + h - 1][j + w - 1] - pre[i + h - 1][j - 1] - pre[i - 1][j + w - 1] + pre[i - 1][j - 1];
            if (sum > (h * w - 1) / 2)
            {
                return true;
            }
        }
    }
    return false;
}

int rectangle(int m, int n, int h, int w, int q[3001][3001])
{
    ::n = n, ::m = m, ::h = h, ::w = w;
    for (lli i = 1; i <= m; i ++)
    {
        for (lli j = 1; j <= n; j ++)
        {
            b[i][j] = q[i - 1][j - 1];
        }
    }
    lli l = 0, r = m * n, res = 0;
    while (l <= r)
    {
        lli mid = (l + r) / 2;
        if (check(mid))
        {
            res = mid;
            r = mid - 1;
        } else l = mid + 1;
        //cout << mid << endl;
    }
    return res;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6588 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6588 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 3 ms 11100 KB Output is correct
5 Correct 3 ms 10952 KB Output is correct
6 Correct 3 ms 11100 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6588 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 3 ms 11100 KB Output is correct
5 Correct 3 ms 10952 KB Output is correct
6 Correct 3 ms 11100 KB Output is correct
7 Correct 21 ms 20828 KB Output is correct
8 Correct 21 ms 20824 KB Output is correct
9 Correct 24 ms 20824 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6588 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 3 ms 11100 KB Output is correct
5 Correct 3 ms 10952 KB Output is correct
6 Correct 3 ms 11100 KB Output is correct
7 Correct 21 ms 20828 KB Output is correct
8 Correct 21 ms 20824 KB Output is correct
9 Correct 24 ms 20824 KB Output is correct
10 Correct 255 ms 65188 KB Output is correct
11 Correct 271 ms 65316 KB Output is correct
12 Correct 130 ms 58884 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6588 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 3 ms 11100 KB Output is correct
5 Correct 3 ms 10952 KB Output is correct
6 Correct 3 ms 11100 KB Output is correct
7 Correct 21 ms 20828 KB Output is correct
8 Correct 21 ms 20824 KB Output is correct
9 Correct 24 ms 20824 KB Output is correct
10 Correct 255 ms 65188 KB Output is correct
11 Correct 271 ms 65316 KB Output is correct
12 Correct 130 ms 58884 KB Output is correct
13 Correct 2457 ms 251852 KB Output is correct
14 Correct 2438 ms 251860 KB Output is correct
15 Correct 2234 ms 243792 KB Output is correct