Submission #1168324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168324		jadai007	Quality Of Living (IOI10_quality)	C++20	100 / 100	1177 ms	70900 KiB

quality

/*
    Author : detective conan
    Problem : IOI10_quality
    Created : 17/03/2025 13:42 UTC+7
*/
#include <bits/stdc++.h>
#include "quality.h"
#define FOR(i, s, t) for(int i = s; i <= t; ++i)
#define rep(i, s, t) for(int i = s; i >= t; --i)
#define DB(n, s) cout << n << s
#define ANS(n, s) DB(n, s)
#define mod 1e9 + 7
#define HAVE_TESTCASE false
#define conan cin.tie(nullptr)->sync_with_stdio(false)
#define sum(a, b) ((a%mod) + (b%mod))%mod
#define mul(a, b) ((a%mod) * (b%mod))
#define pb push_back
#define eb emplace_back
#define em emplace

using namespace std;
using u32 = unsigned;
using i64 = int64_t;
using u64 = unsigned i64;

using namespace std;

//static int R,C,H,W,Q[3001][3001],i,j,ans;

bool check(int R, int C, int H, int W, int Q[3001][3001], int mid){
    #define FOR(i, s, t) for(int i = s; i <= t; ++i)
    #define rep(i, s, t) for(int i = s; i >= t; --i)
    int qs[R + 1][C + 1] = {{0}};
    FOR(i, 1, R){
        FOR(j, 1, C){
            qs[i][j] = (Q[i - 1][j - 1] <= mid);
            qs[i][j] += qs[i - 1][j] + qs[i][j - 1] - qs[i - 1][j - 1];
        }
    }
    FOR(i, H, R) FOR(j, W, C) if(qs[i][j] - qs[i - H][j] - qs[i][j - W] + qs[i - H][j - W] >= (H*W + 1)/2) return true;
    return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]){
    int l = 1, r = R*C, ans = -1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(check(R, C, H, W, Q, mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
	return ans;
}

/*
int main(){
    scanf("%d%d%d%d",&R,&C,&H,&W);
    for (i=0;i<R;i++) for (j=0;j<C;j++) scanf("%d",&Q[i][j]);
    ans = rectangle(R,C,H,W,Q);
    printf("%d\n",ans);
    return 0;
}
*/

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