oj.uz

Submission #800140

# Submission time Handle Problem Language Result Execution time Memory
800140 2023-08-01T10:51:08 Z GoldLight Quality Of Living (IOI10_quality) C++17
100 / 100
 1390 ms 71076 KB 
#include <bits/stdc++.h>
using namespace std;
void fast(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.tie(0);}

int rectangle(int r, int c, int h, int w, int q[3001][3001]){
    fast();
	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 0 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 0 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 1 ms 724 KB Output is correct
5 Correct 1 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 0 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 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 12 ms 2244 KB Output is correct
8 Correct 11 ms 2244 KB Output is correct
9 Correct 12 ms 2180 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 12 ms 2244 KB Output is correct
8 Correct 11 ms 2244 KB Output is correct
9 Correct 12 ms 2180 KB Output is correct
10 Correct 134 ms 12280 KB Output is correct
11 Correct 171 ms 12280 KB Output is correct
12 Correct 69 ms 8308 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 12 ms 2244 KB Output is correct
8 Correct 11 ms 2244 KB Output is correct
9 Correct 12 ms 2180 KB Output is correct
10 Correct 134 ms 12280 KB Output is correct
11 Correct 171 ms 12280 KB Output is correct
12 Correct 69 ms 8308 KB Output is correct
13 Correct 1376 ms 71068 KB Output is correct
14 Correct 1390 ms 71076 KB Output is correct
15 Correct 1290 ms 67532 KB Output is correct