oj.uz

Submission #587189

# Submission time Handle Problem Language Result Execution time Memory
587189 2022-07-01T13:03:39 Z KindaNameless Quality Of Living (IOI10_quality) C++14
100 / 100
 1701 ms 140328 KB 
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<numeric>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<map>
#include<set>

#include "quality.h"

using namespace std;

#define ll long long
#define ld long double

int rectangle(int R, int C, int H, int W, int Q[3001][3001]){
    int l = 0, r = R*C + 1, half = (H*W + 1)/2;
    vector<vector<int>> pref(R, vector<int>(C));
    while(r - l > 1){
        int mid = (l + r) / 2;

        bool exist = 0;
        for(int i = 0; i < R; ++i){
            for(int j = 0; j < C; ++j){
                pref[i][j] = (Q[i][j] <= mid);
                pref[i][j] += (i == 0 ? 0 : pref[i-1][j]) + (j == 0 ? 0 : pref[i][j-1]) - ((i == 0 || j == 0) ? 0 : pref[i-1][j-1]);
            }
        }

        for(int i = H-1; i < R; ++i){
            for(int j = W-1; j < C; ++j){
                int u = i - H + 1, v = j - W + 1;
                int cnt = pref[i][j] - (u == 0 ? 0 : pref[u-1][j]) - (v == 0 ? 0 : pref[i][v-1]) + ((u == 0 || v == 0) ? 0 : pref[u-1][v-1]);
                if(cnt >= half){
                    exist = 1;
                    break;
                }
            }
            if(exist)break;
        }

        if(exist){
            r = mid;
        }
        else l = mid;
    }
    return r;
}

//int main(){
//    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//
//    int R, C, H, W; cin >> R >> C >> H >> W;
//
//    vector<vector<int>> Q(R, vector<int>(C));
//
//    for(int i = 0; i < R; ++i){
//        for(int j = 0; j < C; ++j){
//            cin >> Q[i][j];
//        }
//    }
//
//    cout << rectangle(R, C, H, W, Q);
//
//    return 0;
//}

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 436 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 436 KB Output is correct
4 Correct 2 ms 828 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 1 ms 436 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 2 ms 828 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 16 ms 2668 KB Output is correct
8 Correct 15 ms 2644 KB Output is correct
9 Correct 13 ms 2636 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 436 KB Output is correct
4 Correct 2 ms 828 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 16 ms 2668 KB Output is correct
8 Correct 15 ms 2644 KB Output is correct
9 Correct 13 ms 2636 KB Output is correct
10 Correct 184 ms 18908 KB Output is correct
11 Correct 167 ms 18900 KB Output is correct
12 Correct 107 ms 11464 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 436 KB Output is correct
4 Correct 2 ms 828 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 16 ms 2668 KB Output is correct
8 Correct 15 ms 2644 KB Output is correct
9 Correct 13 ms 2636 KB Output is correct
10 Correct 184 ms 18908 KB Output is correct
11 Correct 167 ms 18900 KB Output is correct
12 Correct 107 ms 11464 KB Output is correct
13 Correct 1701 ms 140256 KB Output is correct
14 Correct 1663 ms 140328 KB Output is correct
15 Correct 1506 ms 129628 KB Output is correct