Submission #1130343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130343		bachnv	Quality Of Living (IOI10_quality)	C++20	100 / 100	1460 ms	106288 KiB

quality

#include <bits/stdc++.h>
using namespace std;
using ll = int;
ll n, m, h, w, x, pfs[3005][3005], q[3005][3005];
ll cmp(ll temp){
    if(temp == x){
        return 0;
    }
    else if(temp < x){
        return 1;
    }
    else{
        return -1;
    }
}
bool check(){
    memset(pfs, 0, sizeof(pfs));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            pfs[i][j] = cmp(q[i][j]);
            if(i){
                pfs[i][j] += pfs[i - 1][j];
            }
            if(j){
                pfs[i][j] += pfs[i][j - 1];
            }
            if(i && j){
                pfs[i][j] -= pfs[i - 1][j - 1];
            }
        }
    }
    for(int i = 0; i + h - 1 < n; i++){
        for(int j = 0; j + w - 1 < m; j++){
            ll temp = pfs[i + h - 1][j + w - 1];
            if(i){
                temp -= pfs[i - 1][j + w - 1];
            }
            if(j){
                temp -= pfs[i + h - 1][j - 1];
            }
            if(i && j){
                temp += pfs[i - 1][j - 1];
            }
            if(temp >= 0){
                return true;
            }
        }
    }
    return false;
}
int rectangle(ll R, ll C, ll H, ll W, ll Q[3001][3001]){
    n = R, m = C, h = H, w = W;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            q[i][j] = Q[i][j];
        }
    }
    ll res;
    ll l = 1, r = n * m;
    while(l <= r){
        x = (l + r) / 2;
        if(check()){
            res = x;
            r = x - 1;
        }
        else{
            l = x + 1;
        }
    }
    return res;
}

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