oj.uz

Submission #511043

# Submission time Handle Problem Language Result Execution time Memory
511043 2022-01-15T04:49:39 Z tabr Quality Of Living (IOI10_quality) C++17
100 / 100
 1679 ms 140260 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

int rectangle(int r, int c, int h, int w, int q[3001][3001]) {
    int low = 0;
    int high = r * c;
    while (high - low > 1) {
        int mid = (high + low) / 2;
        int ok = 0;
        vector<vector<int>> pref(r + 1, vector<int>(c + 1));
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                pref[i + 1][j + 1] = pref[i + 1][j] + pref[i][j + 1] - pref[i][j] + (q[i][j] <= mid);
            }
        }
        for (int i = 0; i <= r - h; i++) {
            for (int j = 0; j <= c - w; j++) {
                if (pref[i + h][j + w] - pref[i][j + w] - pref[i + h][j] + pref[i][j] > h * w / 2) {
                    ok = 1;
                }
            }
        }
        if (ok) {
            high = mid;
        } else {
            low = mid;
        }
    }
    return high;
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int q[3001][3001];
    int r, c, h, w;
    cin >> r >> c >> h >> w;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> q[i][j];
        }
    }
    debug(rectangle(r, c, h, w, q));
    return 0;
}
#endif

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 380 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 2 ms 828 KB Output is correct
6 Correct 2 ms 716 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 380 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 2 ms 828 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 15 ms 2728 KB Output is correct
8 Correct 15 ms 2716 KB Output is correct
9 Correct 13 ms 2692 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 380 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 2 ms 828 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 15 ms 2728 KB Output is correct
8 Correct 15 ms 2716 KB Output is correct
9 Correct 13 ms 2692 KB Output is correct
10 Correct 182 ms 18992 KB Output is correct
11 Correct 213 ms 18948 KB Output is correct
12 Correct 94 ms 11572 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 380 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 2 ms 828 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 15 ms 2728 KB Output is correct
8 Correct 15 ms 2716 KB Output is correct
9 Correct 13 ms 2692 KB Output is correct
10 Correct 182 ms 18992 KB Output is correct
11 Correct 213 ms 18948 KB Output is correct
12 Correct 94 ms 11572 KB Output is correct
13 Correct 1664 ms 140196 KB Output is correct
14 Correct 1679 ms 140260 KB Output is correct
15 Correct 1467 ms 129700 KB Output is correct