Submission #759434

#	Time	Username	Problem	Language	Result	Execution time	Memory
759434		raysh07	Quality Of Living (IOI10_quality)	C++17	0 / 100	1 ms	340 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>
using namespace std;

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	vector<vector<int>> a(R + 1, vector<int>(C + 1));
	for (int i = 1; i <= R; i++){
	    for (int j = 1; j <= C; j++){
	        a[i][j] = Q[i - 1][j - 1];
	    }
	}
	
	int l = 1, r = R * C;
	vector<vector<int>> p(R + 1, vector<int>(C + 1, 0));
	
	while (l != r){
	    int m = (l + r)/2;
	    
	    bool good = false;
	    for (int i = 1; i <= R; i++){
	        for (int j = 1; j <= C; j++){
	            p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
	            if (a[i][j] >= m) p[i][j]++;
	        }
	    }
	    
	    for (int i = 1; i <= R; i++){
	        for (int j = 1; j <= C; j++){
	            int x = i + H - 1;
	            int y = j + W - 1;
	            
	            if (x > R || y > C) continue;
	            
	            int val = p[x][y] + p[i - 1][j - 1] - p[x][j - 1] - p[i - 1][y];
	            if (val > (H * W) / 2) good = true;
	        }
	    }
	    
	    if (good) r = m;
	    else l = m + 1;
	}
	
	return l;
}

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