Submission #335401

#	Time	Username	Problem	Language	Result	Execution time	Memory
335401		Swan	Quality Of Living (IOI10_quality)	C++14	100 / 100	2024 ms	175596 KiB

quality

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

int pref[3001][3001];
int arr[3003][3003];

int sum(int x1, int y1, int x2, int y2){
    return pref[x2][y2] - pref[x2][y1 - 1] - pref[x1 - 1][y2] + pref[x1 - 1][y1 - 1];
}

bool check(int R, int C, int H, int W, int x){
    for(int i = 1; i <= R;i++){
        for(int j = 1; j <= C;j++){
            if(arr[i][j] <= x)pref[i][j] = 1;
            else pref[i][j] = 0;
            pref[i][j]+=pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
        }
    }
    for(int i = 1; i <= R;i++){
        for(int j = 1;j<=C;j++){
            int x2 = i + H - 1;
            int y2 = j + W - 1;
            if(x2 > R || y2 > C)break;
            int rectSum = sum(i, j, x2, y2);
            if(rectSum >= (H * W + 1) / 2)return 1;
        }
    }
    return 0;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int l = 1;
	int r = 1e7;
	for(int i = 1;i <= R;i++){
        for(int j = 1; j <= C;j++){
            arr[i][j] = Q[i - 1][j - 1];
        }
	}
	while(r - l > 1){
        int m = (l + r) / 2;
        if(check(R, C, H, W, m)) r = m;
        else l = m;
	}
	if(l == r){
        return l;
	}else{
        if(check(R, C, H, W, l))return l;
        else return r;
	}
}

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