Submission #383848

#	Time	Username	Problem	Language	Result	Execution time	Memory
383848		MODDI	Quality Of Living (IOI10_quality)	C++14	0 / 100	1 ms	876 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>
#define ll long long
#define	pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back 
using namespace std;
int matrix[3001][3001], n, m, r, c;
bool solve(int fix)
{
    int sum[3001][3001], mat[3001][3001];
    for(int i = 0; i < n; i++){
    	for(int j = 0; j < m; j++){
    		if(matrix[i][j] > fix)
    			mat[i][j] = 1;
    		else if(matrix[i][j] < fix)
    			mat[i][j] = -1;
    		else
    			mat[i][j]=0;
		}
	}
    sum[0][0] = mat[0][0];
    for (int j = 1; j < n; j++) {
        sum[0][j] = mat[0][j] + sum[0][j - 1];
    }
    for (int i = 1; i < m; i++) {
        sum[i][0] = mat[i][0] + sum[i - 1][0];
    }
    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j < m; j++)
        {
            sum[i][j] = mat[i][j] + sum[i - 1][j] + sum[i][j - 1]
                - sum[i - 1][j - 1];
        }
    }
    int total;
    for (int i = r - 1; i < n; i++)
    {
        for (int j = c - 1; j < m; j++)
        {
            total = sum[i][j];
            if (i - r >= 0) {
                total = total - sum[i - r][j];
            }
            if (j - c >= 0) {
                total = total - sum[i][j - c];
            }
            if (i - r >= 0 && j - c >= 0) {
                total = total + sum[i -r][j - c];
            }
            if(total == 0) {
                return true;
            }
        }
    }
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	n = R;
	m = C;
	r = H;
	c = W;
	vi arr;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++){
			matrix[i][j] = Q[i][j];
			arr.pb(Q[i][j]);
		}
		
	sort(arr.begin(), arr.end());
	int l = 0, r = arr.size() - 1, mid,rez;
	while(l <= r){
		int mid = (l + r) / 2;
		bool check = solve(arr[mid]);
		if(check){
			rez = mid;
			r = mid - 1;
		}
		else
			l = mid + 1;
	}
	return arr[rez];
}

Compilation message (stderr)

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:74:33: warning: unused variable 'mid' [-Wunused-variable]
   74 |  int l = 0, r = arr.size() - 1, mid,rez;
      |                                 ^~~
quality.cpp: In function 'bool solve(int)':
quality.cpp:60:1: warning: control reaches end of non-void function [-Wreturn-type]
   60 | }
      | ^
quality.cpp:25:25: warning: 'mat[0][0]' may be used uninitialized in this function [-Wmaybe-uninitialized]
   25 |     sum[0][0] = mat[0][0];
      |                 ~~~~~~~~^
quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:85:16: warning: 'rez' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |  return arr[rez];
      |                ^

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