Submission #245589

#	Time	Username	Problem	Language	Result	Execution time	Memory
245589		tatyam	Quality Of Living (IOI10_quality)	C++17	100 / 100	2310 ms	71160 KiB

quality

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define name3(a,b,c,d,...) d
#define rep1(b) for(int i = 0; i < b; i++)
#define rep2(i,b) for(int i = 0; i < b; i++)
#define rep3(i,a,b) for(int i = a; i < b; i++)
#define rep(...) name3(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
 
int rectangle(int R, int C, int H, int W, int Q[3001][3001]){
    auto check = [&](int x) -> bool {
        vector s(R + 1, vector<int>(C + 1));
        rep(R) rep(j, C) s[i + 1][j + 1] = Q[i][j] <= x;
        rep(R + 1) rep(j, C) s[i][j + 1] += s[i][j];
        rep(R) rep(j, C + 1) s[i + 1][j] += s[i][j];
        rep(i, H, R + 1) rep(j, W, C + 1) if(s[i][j] - s[i - H][j] - s[i][j - W] + s[i - H][j - W] >= (H * W + 1) / 2) return true;
        return false;
    };
    int ok = R * C, ng = 0;
    while(ok - ng > 1){
        int cen = (ok + ng) / 2;
        (check(cen) ? ok : ng) = cen;
    }
    return ok;
}

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