oj.uz

Submission #894869

# Submission time Handle Problem Language Result Execution time Memory
894869 2023-12-29T06:46:06 Z vjudge1 Quality Of Living (IOI10_quality) C++17
100 / 100
 2533 ms 175820 KB 
#include<bits/stdc++.h>
using namespace std;
vector<vector<int>>grid;
bool check(vector<vector<int>>&pref, int R, int C, int H, int W){
    for(int i = 1;i <= R;++i){
        for(int j = 1;j <= C;++j){
            if(i + H - 1 <= R && j + W - 1 <= C){
                int num = pref[i + H - 1][j + W - 1] - pref[i - 1][j + W - 1] - pref[i + H - 1][j - 1] + pref[i - 1][j - 1];
                if(num >= H * W / 2 + 1)return true;
            }
        }
    }
    return false;
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]){
    grid.assign(R + 1, vector<int>(C + 1));
    for(int i = 1;i <= R;++i){
        for(int j = 1;j <= C;++j){
            grid[i][j] = Q[i - 1][j - 1];
        }
    }
    int l = 1, r = R * C, ans = r;
    while(l <= r){
        int mid = (l + r) >> 1;
        vector<vector<int>>pref(R + 1, vector<int>(C + 1));
        for(int i = 1;i <= R;++i){
            for(int j = 1;j <= C;++j){
                if(grid[i][j] <= mid){
                    pref[i][j]++;
                }
                pref[i][j] += pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
            }
        }
        if(check(pref, R, C, H, W)){
            ans = mid;
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    return ans;
}
// int main(){
//     ios_base::sync_with_stdio(0);
//     cin.tie(0);
//     int n, m, H, W;
//     cin >> n >> m >> H >> W;
//     vector<vector<int>>v(n, vector<int>(m));
//     for(int i = 0;i < n;++i){
//         for(int j = 0;j < m;++j){
//             cin >> v[i][j];
//         }
//     }
//     cout << rectangle(n, m, H, W, v);
 
// }

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2484 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2500 KB Output is correct
6 Correct 2 ms 2476 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2484 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2500 KB Output is correct
6 Correct 2 ms 2476 KB Output is correct
7 Correct 17 ms 5836 KB Output is correct
8 Correct 16 ms 5844 KB Output is correct
9 Correct 14 ms 5736 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2484 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2500 KB Output is correct
6 Correct 2 ms 2476 KB Output is correct
7 Correct 17 ms 5836 KB Output is correct
8 Correct 16 ms 5844 KB Output is correct
9 Correct 14 ms 5736 KB Output is correct
10 Correct 203 ms 27520 KB Output is correct
11 Correct 197 ms 27608 KB Output is correct
12 Correct 107 ms 20136 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2484 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 2 ms 2500 KB Output is correct
6 Correct 2 ms 2476 KB Output is correct
7 Correct 17 ms 5836 KB Output is correct
8 Correct 16 ms 5844 KB Output is correct
9 Correct 14 ms 5736 KB Output is correct
10 Correct 203 ms 27520 KB Output is correct
11 Correct 197 ms 27608 KB Output is correct
12 Correct 107 ms 20136 KB Output is correct
13 Correct 2533 ms 175820 KB Output is correct
14 Correct 2063 ms 175664 KB Output is correct
15 Correct 1885 ms 161720 KB Output is correct