# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
383848 | 2021-03-30T21:37:08 Z | MODDI | Quality Of Living (IOI10_quality) | C++14 | 1 ms | 876 KB |
#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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 876 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 876 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 876 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 876 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 876 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |