oj.uz

Submission #252309

# Submission time Handle Problem Language Result Execution time Memory
252309 2020-07-25T08:31:20 Z SamAnd Quality Of Living (IOI10_quality) C++17
100 / 100
 2964 ms 175624 KB 
//#include "quality.h"
#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 3003;

int n, m, h, w;
int a[N][N];

int p[N][N];
bool stg(int x)
{
    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];
            if (a[i][j] <= x)
                ++p[i][j];
        }
    }
    for (int x2 = h; x2 <= n; ++x2)
    {
        for (int y2 = w; y2 <= m; ++y2)
        {
            int x1 = x2 - h;
            int y1_ = y2 - w;
            int q = p[x2][y2] - p[x2][y1_] - p[x1][y2] + p[x1][y1_];
            if (q >= h * w / 2 + 1)
                return true;
        }
    }
    return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
    n = R;
    m = C;
    h = H;
    w = 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 = 1, r = n * m;
    int ans;
    while (l <= r)
    {
        int m = (l + r) / 2;
        if (stg(m))
        {
            ans = m;
            r = m - 1;
        }
        else
            l = m + 1;
    }
    return ans;
}

Compilation message

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:63:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ans;
            ^~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 3 ms 1664 KB Output is correct
6 Correct 5 ms 1664 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 3 ms 1664 KB Output is correct
6 Correct 5 ms 1664 KB Output is correct
7 Correct 28 ms 5496 KB Output is correct
8 Correct 26 ms 5504 KB Output is correct
9 Correct 23 ms 5376 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 3 ms 1664 KB Output is correct
6 Correct 5 ms 1664 KB Output is correct
7 Correct 28 ms 5496 KB Output is correct
8 Correct 26 ms 5504 KB Output is correct
9 Correct 23 ms 5376 KB Output is correct
10 Correct 312 ms 30952 KB Output is correct
11 Correct 309 ms 30840 KB Output is correct
12 Correct 153 ms 21496 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 3 ms 1664 KB Output is correct
6 Correct 5 ms 1664 KB Output is correct
7 Correct 28 ms 5496 KB Output is correct
8 Correct 26 ms 5504 KB Output is correct
9 Correct 23 ms 5376 KB Output is correct
10 Correct 312 ms 30952 KB Output is correct
11 Correct 309 ms 30840 KB Output is correct
12 Correct 153 ms 21496 KB Output is correct
13 Correct 2964 ms 175624 KB Output is correct
14 Correct 2920 ms 175600 KB Output is correct
15 Correct 2682 ms 168504 KB Output is correct