Submission #1181098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181098		hamzabc	Quality Of Living (IOI10_quality)	C++20	100 / 100	1825 ms	106260 KiB

quality

#ifndef LOCAL
#include "quality.h"
#endif
#include <bits/stdc++.h>


using namespace std;


int harita[3001][3001], r, c, h, w;


bool check(int m){
    vector<vector<int>> prefix(r + 1, vector<int>(c + 1, 0));
    for (int i = 1; i <= r; i++){
        for (int o = 1; o <= c; o++){
            if (harita[i - 1][o - 1] <= m)
                prefix[i][o] += 1;
            prefix[i][o] += prefix[i - 1][o];
            prefix[i][o] += prefix[i][o - 1];
            prefix[i][o] -= prefix[i - 1][o - 1];
        }
    }
    for (int i = 0; i <= r - h; i++){
        for (int o = 0; o <= c - w; o++){
            if (prefix[i + h][o + w] - prefix[i][o + w] - prefix[i + h][o] + prefix[i][o] >= (w * h + 1) / 2){
                return true;
            }
        }
    }
    return false;
}


int divandq(int tl, int tr){
    if (tl == tr)
        return tl;
    int m = (tl + tr) >> 1;
    if (check(m)){
        return divandq(tl, m);
    }else{
        return divandq(m + 1, tr);
    }
}


int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	for (int i = 0; i < R; i++){
        for (int o = 0; o < C; o++){
            harita[i][o] = Q[i][o];
        }
    }
    r = R;
    c = C;
    h = H;
    w = W;
    return divandq((H * W + 1) >> 1, R * C / 2 + 1);
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20