oj.uz

Submission #595777

# Submission time Handle Problem Language Result Execution time Memory
595777 2022-07-14T06:27:53 Z snasibov05 Quality Of Living (IOI10_quality) C++14
100 / 100
 2394 ms 72952 KB 
#include "quality.h"
#include "bits/stdc++.h"

using namespace std;

bool check(int k, int r, int c, int h, int w, int q[3001][3001]){

    vector<vector<int>> cntp(r, vector<int>(c));
    for (int i = 0; i < r; ++i){
        for (int j = 0; j < c; ++j){
            if (i != 0) cntp[i][j] += cntp[i-1][j];
            if (j != 0) cntp[i][j] += cntp[i][j-1];
            if (i != 0 && j != 0) cntp[i][j] -= cntp[i-1][j-1];
            cntp[i][j] += q[i][j] <= k;
        }
    }

    for (int i = h-1; i < r; ++i){
        for (int j = w-1; j < c; ++j){
            int cnt = cntp[i][j];
            if (i != h-1) cnt -= cntp[i - h][j];
            if (j != w-1) cnt -= cntp[i][j - w];
            if (i != h-1 && j != w-1) cnt += cntp[i - h][j - w];
            if (cnt > h * w / 2) return true;
        }
    }

    return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {

    int l = 1, r = R*C;
    int bst = 0;
    while (l <= r){
        int mid = (l + r) / 2;
        if (check(mid, R, C, H, W, Q)) bst = mid, r = mid - 1;
        else l = mid + 1;
    }

    return bst;

}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 19 ms 2220 KB Output is correct
8 Correct 19 ms 2752 KB Output is correct
9 Correct 19 ms 2620 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 19 ms 2220 KB Output is correct
8 Correct 19 ms 2752 KB Output is correct
9 Correct 19 ms 2620 KB Output is correct
10 Correct 237 ms 18932 KB Output is correct
11 Correct 268 ms 19004 KB Output is correct
12 Correct 118 ms 11664 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 19 ms 2220 KB Output is correct
8 Correct 19 ms 2752 KB Output is correct
9 Correct 19 ms 2620 KB Output is correct
10 Correct 237 ms 18932 KB Output is correct
11 Correct 268 ms 19004 KB Output is correct
12 Correct 118 ms 11664 KB Output is correct
13 Correct 2394 ms 72836 KB Output is correct
14 Correct 2365 ms 72952 KB Output is correct
15 Correct 2168 ms 69012 KB Output is correct