Submission #759437

#	Time	Username	Problem	Language	Result	Execution time	Memory
759437		raysh07	Quality Of Living (IOI10_quality)	C++17	100 / 100	1950 ms	155888 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]++;
	            //    cout << i << " " << j << "\n";
	            }
	        }
	    }
	    
	   // cout << m << "\n";
	   // for (int i = 1; i <= R; i++){
	   //     for (int j = 1; j <= C; j++){
	   //         cout << p[i][j] << " \n"[j == C];
	   //     }
	   // }
	    
	    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;
}

// int main(){
//     int r, c, h, w; int Q[3001][3001];
    
//     cin >> r >> c >> h >> w;
    
//     for (int i = 1; i <= r; i++){
//         for (int j = 1; j <= c; j++){
//             cin >> Q[i - 1][j - 1];
//         }
//     }
    
//     cout << rectangle(r, c, h, w, Q);
//     return 0;
// }

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