Submission #802160

#	Time	Username	Problem	Language	Result	Execution time	Memory
802160		Liudas	Quality Of Living (IOI10_quality)	C++17	100 / 100	1472 ms	115096 KiB

quality

#include <bits/stdc++.h>
#include "quality.h"
using namespace std;
int rectangle(int R, int C, int H, int W, int Q[][3001]){
    int l = 0, r = R * C;
    while(l < r){
        int mid = (l + r) / 2;
        vector<vector<int>> p(R+ 1, vector<int>(C + 1));
        for(int i = 0; i < R; i ++){
            for(int j = 0; j < C; j ++){
                p[i+1][j+1] = p[i][j+1] + p[i+1][j] - p[i][j] + (Q[i][j] <= mid);
            }
        }
        int ans = 0;
        for(int i = H; i < R + 1; i++){
            for(int j = W; j < C + 1; j++){
                ans = max(ans, p[i][j]-p[i-H][j]-p[i][j-W] + p[i-H][j-W]);
            }
        }
        if(ans * 2 >= H * W){
            r = mid;
        }
        else{
            l = mid + 1;
        }
    }
    return l;
}

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