oj.uz

Submission #893894

# Submission time Handle Problem Language Result Execution time Memory
893894 2023-12-27T16:36:30 Z Irate Quality Of Living (IOI10_quality) C++14
100 / 100
 2112 ms 176060 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 2392 KB Output is correct
2 Correct 1 ms 2396 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 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 3 ms 2748 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 3 ms 2748 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 16 ms 5852 KB Output is correct
8 Correct 16 ms 5912 KB Output is correct
9 Correct 17 ms 5756 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 3 ms 2748 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 16 ms 5852 KB Output is correct
8 Correct 16 ms 5912 KB Output is correct
9 Correct 17 ms 5756 KB Output is correct
10 Correct 200 ms 27620 KB Output is correct
11 Correct 206 ms 27632 KB Output is correct
12 Correct 108 ms 20124 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 3 ms 2748 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 16 ms 5852 KB Output is correct
8 Correct 16 ms 5912 KB Output is correct
9 Correct 17 ms 5756 KB Output is correct
10 Correct 200 ms 27620 KB Output is correct
11 Correct 206 ms 27632 KB Output is correct
12 Correct 108 ms 20124 KB Output is correct
13 Correct 2112 ms 176060 KB Output is correct
14 Correct 2052 ms 175972 KB Output is correct
15 Correct 1927 ms 161848 KB Output is correct