oj.uz

Submission #925510

# Submission time Handle Problem Language Result Execution time Memory
925510 2024-02-11T20:41:33 Z VMaksimoski008 Quality Of Living (IOI10_quality) C++14
100 / 100
 1176 ms 70896 KB 
#include <iostream>
#include "quality.h"
#pragma GCC optimize("O2,unroll-loops")
using namespace std;

int rectangle(int n, int m, int h, int w, int q[3001][3001]) {
    int l=(h*w+1)/2, r=n*m-(h*w)/2, ans=0, pref[3001][3001];

    while(l <= r) {
        int M = (l + r) / 2;
        bool ok = 0;

        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                pref[i][j] = (q[i-1][j-1] <= M) + 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(2 * (pref[i+h-1][j+w-1] - pref[i-1][j+w-1] - pref[i+h-1][j-1] + pref[i-1][j-1]) >= h * w) ok = 1;

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

    return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 37720 KB Output is correct
2 Correct 18 ms 37724 KB Output is correct
3 Correct 17 ms 37724 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 37720 KB Output is correct
2 Correct 18 ms 37724 KB Output is correct
3 Correct 17 ms 37724 KB Output is correct
4 Correct 18 ms 37732 KB Output is correct
5 Correct 24 ms 37720 KB Output is correct
6 Correct 19 ms 37604 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 37720 KB Output is correct
2 Correct 18 ms 37724 KB Output is correct
3 Correct 17 ms 37724 KB Output is correct
4 Correct 18 ms 37732 KB Output is correct
5 Correct 24 ms 37720 KB Output is correct
6 Correct 19 ms 37604 KB Output is correct
7 Correct 27 ms 39764 KB Output is correct
8 Correct 26 ms 39772 KB Output is correct
9 Correct 26 ms 39808 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 37720 KB Output is correct
2 Correct 18 ms 37724 KB Output is correct
3 Correct 17 ms 37724 KB Output is correct
4 Correct 18 ms 37732 KB Output is correct
5 Correct 24 ms 37720 KB Output is correct
6 Correct 19 ms 37604 KB Output is correct
7 Correct 27 ms 39764 KB Output is correct
8 Correct 26 ms 39772 KB Output is correct
9 Correct 26 ms 39808 KB Output is correct
10 Correct 136 ms 47956 KB Output is correct
11 Correct 126 ms 47956 KB Output is correct
12 Correct 76 ms 47896 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 37720 KB Output is correct
2 Correct 18 ms 37724 KB Output is correct
3 Correct 17 ms 37724 KB Output is correct
4 Correct 18 ms 37732 KB Output is correct
5 Correct 24 ms 37720 KB Output is correct
6 Correct 19 ms 37604 KB Output is correct
7 Correct 27 ms 39764 KB Output is correct
8 Correct 26 ms 39772 KB Output is correct
9 Correct 26 ms 39808 KB Output is correct
10 Correct 136 ms 47956 KB Output is correct
11 Correct 126 ms 47956 KB Output is correct
12 Correct 76 ms 47896 KB Output is correct
13 Correct 1176 ms 70896 KB Output is correct
14 Correct 1148 ms 70796 KB Output is correct
15 Correct 1107 ms 70880 KB Output is correct