oj.uz

Submission #800133

# Submission time Handle Problem Language Result Execution time Memory
800133 2023-08-01T10:45:45 Z GoldLight Quality Of Living (IOI10_quality) C++17
100 / 100
 1328 ms 140368 KB 
#include <bits/stdc++.h>
using namespace std;

int rectangle(int r, int c, int h, int w, int q[3001][3001]) {
	int n=r*c, m=h*w;
    int ans=n, ki=1, ka=n;
    while(ki<=ka){
        int mid=(ki+ka)/2;
        vector<vector<int>> pref(r+1, vector<int>(c+1, 0));
        bool cek=false;
        //count qij<=mid
        for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                pref[i+1][j+1]=(q[i][j]<=mid)+pref[i][j+1]+pref[i+1][j]-pref[i][j];
                if(i>=h-1 && j>=w-1 && pref[i+1][j+1]-pref[i-h+1][j+1]-pref[i+1][j-w+1]+pref[i-h+1][j-w+1]>=m/2+1){
                    cek=true;
                    break;
                }
            }
        }
        if(cek){
            ans=mid;
            ka=mid-1;
        }
        else ki=mid+1;
    }
    return ans;
}
// int main(){
//     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];
//         }
//     }
//     cout<<rectangle(r, c, h, w);
// }

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 1 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 1 ms 436 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 828 KB Output is correct
5 Correct 2 ms 828 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 1 ms 436 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 828 KB Output is correct
5 Correct 2 ms 828 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 11 ms 2744 KB Output is correct
8 Correct 11 ms 2744 KB Output is correct
9 Correct 10 ms 2628 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 1 ms 436 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 828 KB Output is correct
5 Correct 2 ms 828 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 11 ms 2744 KB Output is correct
8 Correct 11 ms 2744 KB Output is correct
9 Correct 10 ms 2628 KB Output is correct
10 Correct 128 ms 18980 KB Output is correct
11 Correct 138 ms 18976 KB Output is correct
12 Correct 65 ms 11608 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 1 ms 436 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 828 KB Output is correct
5 Correct 2 ms 828 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 11 ms 2744 KB Output is correct
8 Correct 11 ms 2744 KB Output is correct
9 Correct 10 ms 2628 KB Output is correct
10 Correct 128 ms 18980 KB Output is correct
11 Correct 138 ms 18976 KB Output is correct
12 Correct 65 ms 11608 KB Output is correct
13 Correct 1328 ms 140228 KB Output is correct
14 Correct 1311 ms 140368 KB Output is correct
15 Correct 1219 ms 129800 KB Output is correct