제출 #1231584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231584		IBMG	삶의 질 (IOI10_quality)	C++20	100 / 100	2251 ms	71020 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>
 
using namespace std;
 
#define ffor(i,o,f)        for(int i = o; i < f; i++)
#define bfor(i,f,o)        for(int i = f; i >= o; i--)
#define pb                 push_back
#define all(a)             (a).begin(), (a).end()
#define F                  first
#define S                  second
#define PI                 acos(-1)
#define endl               '\n'
typedef long long          ll;
typedef long double        ld;  
typedef pair < ll, ll >    pll;
typedef vector < ll >      vll;
const int INF = int(1e9 + 7);
const int MOD = 998244353;
const double EPS = double(1e-9);
const int TAM = 200005;

bool ok(int mid, int q[3001][3001], int r, int c, int h, int w){
    vector<vector<int> > aux(r+1, vector<int>(c+1, 0));
    ffor(i, 1, r+1){
        ffor(j, 1, c+1){
            if(q[i-1][j-1] < mid) aux[i][j] = -1;
            else if(q[i-1][j-1] == mid) aux[i][j] = 0;
            else aux[i][j] = 1;
        }
    }
    ffor(i, 1, r+1){
        ffor(j, 1, c+1) aux[i][j] += aux[i-1][j] + aux[i][j-1] - aux[i-1][j-1];
    }
    ffor(i, h, r+1){
        ffor(j, w, c+1){
            if(aux[i][j] - aux[i-h][j] - aux[i][j-w] + aux[i-h][j-w] <= 0) return true;
        }
    }
    return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]){
    int n = R*C;
    int lo = 1, hi = n, mid, ans = -1;
    while(lo <= hi){
        mid = (lo+hi) / 2;
        if(ok(mid, Q, R, C, H, W)){
            ans = mid;
            hi = mid - 1;
        }
        else lo = mid + 1;
    }
    return ans;
}

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