oj.uz

Submission #925499

# Submission time Handle Problem Language Result Execution time Memory
925499 2024-02-11T20:27:51 Z VMaksimoski008 Quality Of Living (IOI10_quality) C++14
100 / 100
 1320 ms 140352 KB 
#include <bits/stdc++.h>
#include "quality.h"
using namespace std;

int pref[3001][3001];

int rectangle(int n, int m, int h, int w, int q[3001][3001]) {
    int l=0, r=1e9, ans = 0;

    while(l <= r) {
        int mid = (l + r) / 2;
        bool ok = 0;
        memset(pref, 0, sizeof(pref));

        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                pref[i][j] = (q[i-1][j-1] <= mid) + pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];

        for(int i=1; i+h-1<=n; i++)
            for(int j=1; j+w-1<=m; j++)
                if(2ll * (pref[i+h-1][j+w-1] - pref[i-1][j+w-1] - pref[i+h-1][j-1] + pref[i-1][j-1]) >= 1ll * h * w) ok = 1;

        if(ok) ans = mid, r = mid - 1;
        else l = mid + 1;
    }

    return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 37468 KB Output is correct
2 Correct 78 ms 37532 KB Output is correct
3 Correct 77 ms 37716 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 37468 KB Output is correct
2 Correct 78 ms 37532 KB Output is correct
3 Correct 77 ms 37716 KB Output is correct
4 Correct 84 ms 37468 KB Output is correct
5 Correct 78 ms 37464 KB Output is correct
6 Correct 78 ms 37576 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 37468 KB Output is correct
2 Correct 78 ms 37532 KB Output is correct
3 Correct 77 ms 37716 KB Output is correct
4 Correct 84 ms 37468 KB Output is correct
5 Correct 78 ms 37464 KB Output is correct
6 Correct 78 ms 37576 KB Output is correct
7 Correct 89 ms 40096 KB Output is correct
8 Correct 89 ms 40024 KB Output is correct
9 Correct 91 ms 40028 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 37468 KB Output is correct
2 Correct 78 ms 37532 KB Output is correct
3 Correct 77 ms 37716 KB Output is correct
4 Correct 84 ms 37468 KB Output is correct
5 Correct 78 ms 37464 KB Output is correct
6 Correct 78 ms 37576 KB Output is correct
7 Correct 89 ms 40096 KB Output is correct
8 Correct 89 ms 40024 KB Output is correct
9 Correct 91 ms 40028 KB Output is correct
10 Correct 209 ms 54356 KB Output is correct
11 Correct 222 ms 54684 KB Output is correct
12 Correct 146 ms 51100 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 37468 KB Output is correct
2 Correct 78 ms 37532 KB Output is correct
3 Correct 77 ms 37716 KB Output is correct
4 Correct 84 ms 37468 KB Output is correct
5 Correct 78 ms 37464 KB Output is correct
6 Correct 78 ms 37576 KB Output is correct
7 Correct 89 ms 40096 KB Output is correct
8 Correct 89 ms 40024 KB Output is correct
9 Correct 91 ms 40028 KB Output is correct
10 Correct 209 ms 54356 KB Output is correct
11 Correct 222 ms 54684 KB Output is correct
12 Correct 146 ms 51100 KB Output is correct
13 Correct 1320 ms 140352 KB Output is correct
14 Correct 1216 ms 140132 KB Output is correct
15 Correct 1270 ms 133284 KB Output is correct