Submission #734890

# Submission time Handle Problem Language Result Execution time Memory
734890 2023-05-03T08:19:11 Z phoebe Quality Of Living (IOI10_quality) C++17
100 / 100
1761 ms 122328 KB
#include <bits/stdc++.h>
#include "quality.h"
using namespace std;

int prefix[3001][3001] = {0};

int rectangle(int R, int C, int H, int W, int Q[3001][3001]){
    int l = 0, r = 3001 * 3001, ans;
    while (l <= r){
        int mid = (l + r) / 2;
        for (int i = 1; i <= R; i++){
            for (int j = 1; j <= C; j++){
                if (Q[i - 1][j - 1] <= mid) prefix[i][j] = 1;
                else prefix[i][j] = -1;
                prefix[i][j] += prefix[i][j - 1];
            }
        }
        for (int i = 1; i <= R; i++){
            for (int j = 1; j <= C; j++) 
                prefix[i][j] += prefix[i - 1][j];
        }
        bool pos = false;
        for (int i = H; i <= R; i++){
            for (int j = W; j <= C; j++){
                int val = prefix[i][j] - prefix[i - H][j] 
                - prefix[i][j - W] + prefix[i - H][j - W];
                if (val > 0) pos = true;
            }
        }
        if (pos) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    return ans;
}

Compilation message

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:33:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   33 |     return ans;
      |            ^~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 3 ms 1220 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 3 ms 1220 KB Output is correct
7 Correct 19 ms 3536 KB Output is correct
8 Correct 19 ms 3572 KB Output is correct
9 Correct 17 ms 3540 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 3 ms 1220 KB Output is correct
7 Correct 19 ms 3536 KB Output is correct
8 Correct 19 ms 3572 KB Output is correct
9 Correct 17 ms 3540 KB Output is correct
10 Correct 190 ms 16224 KB Output is correct
11 Correct 189 ms 22768 KB Output is correct
12 Correct 135 ms 15512 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 3 ms 1108 KB Output is correct
6 Correct 3 ms 1220 KB Output is correct
7 Correct 19 ms 3536 KB Output is correct
8 Correct 19 ms 3572 KB Output is correct
9 Correct 17 ms 3540 KB Output is correct
10 Correct 190 ms 16224 KB Output is correct
11 Correct 189 ms 22768 KB Output is correct
12 Correct 135 ms 15512 KB Output is correct
13 Correct 1761 ms 122328 KB Output is correct
14 Correct 1687 ms 122320 KB Output is correct
15 Correct 1613 ms 120552 KB Output is correct