# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
832551 | 2023-08-21T11:36:30 Z | SAAD | Quality Of Living (IOI10_quality) | C++17 | 50 ms | 44500 KB |
#define F first #define S second #define rep(i,a,b) for(int i=a;!(a==b&&i!=b)&&((i<=b&&b>=a)||(i>=b&&a>=b));i+=(a<=b?1:-1)) #define pb push_back #define Fbitl __builtin_ffs #define bit1 __builtin_popcount #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <math.h> #include <algorithm> #include <string.h> #include <vector> #include <iomanip> #include <string> #include <queue> #include <map> #include <unordered_map> #include <unordered_set> #include "quality.h" using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<string, string> pss; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<pii> vii; typedef vector<ll> vl; typedef vector<vl> vvl; /*int rectangle(int R, int C, int H, int W, int Q[3001][3001]) { return R * C / 2; } static int R, C, H, W, Q[3001][3001], i, j, ans; int main() { cin >> R >> C >> H >> W ; for (i = 0; i < R; i++) for (j = 0; j < C; j++) cin >> Q[i][j]; ans = rectangle(R, C, H, W, Q); printf("%d\n", ans); return 0; }*/ bool q[3001][3001]; int cm[3001][3001]; int ps[3001][3001]; pii psof[(int)1e7]; static int R, C, H, W, Q[3001][3001], i, j, ans; bool test( int idx ) { memset(q,false,sizeof(q)); memset(cm, 0, sizeof(cm)); for (int i = 1; i <= idx; i++) { q[psof[i].F][psof[i].S] = true; } int target = (H * W)/2 + 1; bool th = false; for (int i = 1; i <= R; i++) { for (int j = 1; j <= C; j++) { cm[i][j] = (q[i][j] ? 1 : 0) + (cm[i][j - 1] + cm[i - 1][j] - cm[i - 1][j - 1]); if (i >= H && j >= W) { int sum = 0; sum = cm[i][j] + cm[i - H][j - W] - (cm[i-H][j]+cm[i][j-W]); if (sum >= target) { th = true; } } } } return th; } int rectangle(int R, int C, int H, int W, int Q[3001][3001]) { int l = 1, r = R * C , md ; for (int i = 0; i < R; i++) { for (int j = 0; j < C; j++) { ps[i + 1][j + 1] = Q[i][j]; psof[Q[i][j]] = {i+1,j+1}; } } while (r > l ) { int ll = l, rr = r; md = (r + l) / 2; if (test(md)) { r = md - 1; } else { l = md ; } if (ll == l && rr == r) break; } md = l+1; return md; } /*int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); scanf("%d%d%d%d", &R, &C, &H, &W); for (i = 0; i < R; i++) for (j = 0; j < C; j++) scanf("%d", &Q[i][j]); ans = rectangle(R, C, H, W, Q); printf("%d\n", ans); return 0; }*/
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 50 ms | 44500 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 50 ms | 44500 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 50 ms | 44500 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 50 ms | 44500 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 50 ms | 44500 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |