oj.uz

Submission #519503

# Submission time Handle Problem Language Result Execution time Memory
519503 2022-01-26T12:57:43 Z fabijan_cikac Quality Of Living (IOI10_quality) C++17
100 / 100
 2121 ms 101456 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3001;

int pref[MAXN][MAXN];
bool check(int x, int n, int m, int h, int w, int a[MAXN][MAXN]){
    int px, py;
    for (int i = 0; i <= max(n, m); ++i){
        pref[0][i] = 0; pref[i][0] = 0;
    }
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
            if (a[i - 1][j - 1] < x)
                --pref[i][j];
            else if (a[i - 1][j - 1] > x)
                ++pref[i][j];
            else{
                px = i; py = j;
            }
         }
    }
    for (int i = 1; i <= n - h + 1; ++i){
        for (int j = 1; j <= m - w + 1; ++j){
            if ((pref[i + h - 1][j + w - 1] - pref[i - 1][j + w - 1] - pref[i + h - 1][j - 1] + pref[i - 1][j - 1] == 0 && (px >= i && px <= i + h - 1 && py >= j && py <= j + w - 1)) || pref[i + h - 1][j + w - 1] - pref[i - 1][j + w - 1] - pref[i + h - 1][j - 1] + pref[i - 1][j - 1] < 0)
                return 1;
        }
    }
    return 0;
}

int bins(int l, int r, int n, int m, int h, int w, int a[MAXN][MAXN]){
    int mid = (l + r - 1) / 2;
    if (l == r)
        return l;
    else if (check(mid, n, m, h, w, a))
        return bins(l, mid, n, m, h, w, a);
    return bins(mid + 1, r, n, m, h, w, a);
}

int rectangle(int R, int C, int H, int W, int Q[MAXN][MAXN]){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    return bins(1, R * C, R, C, H, W, Q);
}

Compilation message

quality.cpp: In function 'bool check(int, int, int, int, int, int (*)[3001])':
quality.cpp:27:163: warning: 'py' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |             if ((pref[i + h - 1][j + w - 1] - pref[i - 1][j + w - 1] - pref[i + h - 1][j - 1] + pref[i - 1][j - 1] == 0 && (px >= i && px <= i + h - 1 && py >= j && py <= j + w - 1)) || pref[i + h - 1][j + w - 1] - pref[i - 1][j + w - 1] - pref[i + h - 1][j - 1] + pref[i - 1][j - 1] < 0)
      |                                                                                                                            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
quality.cpp:27:121: warning: 'px' may be used uninitialized in this function [-Wmaybe-uninitialized]
   27 |             if ((pref[i + h - 1][j + w - 1] - pref[i - 1][j + w - 1] - pref[i + h - 1][j - 1] + pref[i - 1][j - 1] == 0 && (px >= i && px <= i + h - 1 && py >= j && py <= j + w - 1)) || pref[i + h - 1][j + w - 1] - pref[i - 1][j + w - 1] - pref[i + h - 1][j - 1] + pref[i - 1][j - 1] < 0)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 536 KB Output is correct
3 Correct 1 ms 460 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 536 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 2 ms 1204 KB Output is correct
5 Correct 3 ms 1216 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 536 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 2 ms 1204 KB Output is correct
5 Correct 3 ms 1216 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct
7 Correct 16 ms 3896 KB Output is correct
8 Correct 17 ms 3912 KB Output is correct
9 Correct 16 ms 3824 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 536 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 2 ms 1204 KB Output is correct
5 Correct 3 ms 1216 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct
7 Correct 16 ms 3896 KB Output is correct
8 Correct 17 ms 3912 KB Output is correct
9 Correct 16 ms 3824 KB Output is correct
10 Correct 206 ms 22880 KB Output is correct
11 Correct 213 ms 22872 KB Output is correct
12 Correct 117 ms 15464 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 536 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 2 ms 1204 KB Output is correct
5 Correct 3 ms 1216 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct
7 Correct 16 ms 3896 KB Output is correct
8 Correct 17 ms 3912 KB Output is correct
9 Correct 16 ms 3824 KB Output is correct
10 Correct 206 ms 22880 KB Output is correct
11 Correct 213 ms 22872 KB Output is correct
12 Correct 117 ms 15464 KB Output is correct
13 Correct 2121 ms 101456 KB Output is correct
14 Correct 2033 ms 100072 KB Output is correct
15 Correct 1885 ms 96880 KB Output is correct