oj.uz

Submission #390742

# Submission time Handle Problem Language Result Execution time Memory
390742 2021-04-16T20:13:27 Z Sorting Quality Of Living (IOI10_quality) C++17
100 / 100
 2258 ms 106156 KB 
#include "quality.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 3000 + 3;

int q[N][N];
int r, c, h, w;
int a[N][N];

int query(int x1, int y1, int x2, int y2){
    return a[x2][y2] - a[x1 - 1][y2] - a[x2][y1 - 1] + a[x1 - 1][y1 - 1];
}

bool check(int mid){
    for(int i = 1; i <= r; ++i)
        fill(a[i] + 1, a[i] + 1 + c, 0);

    for(int i = 1; i <= r; ++i)
        for(int j = 1; j <= c; ++j)
            a[i][j] = a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1] + (q[i][j] <= mid);

    for(int i = 1; i <= r - h + 1; ++i)
        for(int j = 1; j <= c - w + 1; ++j)
            if(query(i, j, i + h - 1, j + w - 1) >= h * w / 2 + 1)
                return true;
    return false;
}

int rectangle(int _r, int _c, int _h, int _w, int _q[3001][3001]) {
    r = _r, c = _c, h = _h, w = _w;
    for(int i = 1; i <= r; ++i)
        for(int j = 1; j <= c; ++j)
            q[i][j] = _q[i - 1][j - 1];

    int l_bs = 1, r_bs = r * c;
    while(l_bs != r_bs){
        int mid = (l_bs + r_bs) >> 1;
        if(check(mid)) r_bs = mid;
        else l_bs = mid + 1;
    }
    return l_bs;
}
/*
5 5 3 3
5 11 12 16 25
17 18 2 7 10
4 23 20 3 1
24 21 19 14 9
6 22 8 13 15
*/

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct
7 Correct 20 ms 4940 KB Output is correct
8 Correct 24 ms 4972 KB Output is correct
9 Correct 19 ms 4880 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct
7 Correct 20 ms 4940 KB Output is correct
8 Correct 24 ms 4972 KB Output is correct
9 Correct 19 ms 4880 KB Output is correct
10 Correct 236 ms 24004 KB Output is correct
11 Correct 231 ms 24068 KB Output is correct
12 Correct 122 ms 18292 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 3 ms 1612 KB Output is correct
5 Correct 3 ms 1612 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct
7 Correct 20 ms 4940 KB Output is correct
8 Correct 24 ms 4972 KB Output is correct
9 Correct 19 ms 4880 KB Output is correct
10 Correct 236 ms 24004 KB Output is correct
11 Correct 231 ms 24068 KB Output is correct
12 Correct 122 ms 18292 KB Output is correct
13 Correct 2258 ms 106144 KB Output is correct
14 Correct 2201 ms 106156 KB Output is correct
15 Correct 2067 ms 106084 KB Output is correct