oj.uz

Submission #538739

# Submission time Handle Problem Language Result Execution time Memory
538739 2022-03-17T16:10:31 Z joshualiu555 Quality Of Living (IOI10_quality) C++17
100 / 100
 1956 ms 83868 KB 
#include "grader.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, x, n) for (int i = x; i <= n; i++)
#define mem(a, x) memset(a, x, sizeof(a))

bool check(int R, int C, int H, int W, int Q[3001][3001], int median) {
    int ps[3001][3001];
    mem(ps, 0);

    FOR(i, 1, R) {
        FOR(j, 1, C) {
            if (Q[i - 1][j - 1] <= median) {
                ps[i][j] = 1;
            } else {
                ps[i][j] = -1;
            }
        }
    }

    FOR(i, 1, R) {
        FOR(j, 1, C) {
            ps[i][j] += ps[i][j - 1] + ps[i - 1][j] - ps[i - 1][j - 1];
        }
    }

    FOR(i, H, R) {
        FOR(j, W, C) {
            if (ps[i][j] - ps[i - H][j] - ps[i][j - W] + ps[i - H][j - W] > 0) {
                return true;
            }
        }
    }

    return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    int ans = -1;
    int l = 1, r = R * C;
    while (l <= r) {
        int m = (l + r) / 2;
        if (check(R, C, H, W, Q, m)) {
            ans = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }

    return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 35668 KB Output is correct
2 Correct 56 ms 35652 KB Output is correct
3 Correct 64 ms 35612 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 35668 KB Output is correct
2 Correct 56 ms 35652 KB Output is correct
3 Correct 64 ms 35612 KB Output is correct
4 Correct 78 ms 35916 KB Output is correct
5 Correct 71 ms 35924 KB Output is correct
6 Correct 79 ms 36032 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 35668 KB Output is correct
2 Correct 56 ms 35652 KB Output is correct
3 Correct 64 ms 35612 KB Output is correct
4 Correct 78 ms 35916 KB Output is correct
5 Correct 71 ms 35924 KB Output is correct
6 Correct 79 ms 36032 KB Output is correct
7 Correct 99 ms 37608 KB Output is correct
8 Correct 105 ms 37612 KB Output is correct
9 Correct 106 ms 37528 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 35668 KB Output is correct
2 Correct 56 ms 35652 KB Output is correct
3 Correct 64 ms 35612 KB Output is correct
4 Correct 78 ms 35916 KB Output is correct
5 Correct 71 ms 35924 KB Output is correct
6 Correct 79 ms 36032 KB Output is correct
7 Correct 99 ms 37608 KB Output is correct
8 Correct 105 ms 37612 KB Output is correct
9 Correct 106 ms 37528 KB Output is correct
10 Correct 285 ms 50176 KB Output is correct
11 Correct 318 ms 50176 KB Output is correct
12 Correct 188 ms 44748 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 35668 KB Output is correct
2 Correct 56 ms 35652 KB Output is correct
3 Correct 64 ms 35612 KB Output is correct
4 Correct 78 ms 35916 KB Output is correct
5 Correct 71 ms 35924 KB Output is correct
6 Correct 79 ms 36032 KB Output is correct
7 Correct 99 ms 37608 KB Output is correct
8 Correct 105 ms 37612 KB Output is correct
9 Correct 106 ms 37528 KB Output is correct
10 Correct 285 ms 50176 KB Output is correct
11 Correct 318 ms 50176 KB Output is correct
12 Correct 188 ms 44748 KB Output is correct
13 Correct 1865 ms 83724 KB Output is correct
14 Correct 1956 ms 83868 KB Output is correct
15 Correct 1805 ms 82648 KB Output is correct