oj.uz

Submission #262226

# Submission time Handle Problem Language Result Execution time Memory
262226 2020-08-12T13:43:53 Z Alexa2001 Quality Of Living (IOI10_quality) C++17
100 / 100
 2423 ms 140628 KB 
#include "quality.h"
#include <bits/stdc++.h>

using namespace std;

int n, m, r, c, s[3001][3001];

bool check(int val, int a[3001][3001])
{
    int i, j;

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
        {
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + (a[i-1][j-1] <= val ? 1 : -1);

            if(i >= r && j >= c)
                if(s[i][j] - s[i-r][j] - s[i][j-c] + s[i-r][j-c] >= 0)
                    return 1;
        }
    return 0;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001])
{
    int st, dr, mid;
    st = 1; dr = R * C;
    n = R; m = C;
    r = H; c = W;

    while(st <= dr)
    {
        mid = (st + dr) / 2;
        if(check(mid, Q)) dr = mid - 1;
            else st = mid + 1;
    }

    return st;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 ms 1280 KB Output is correct
5 Correct 3 ms 1280 KB Output is correct
6 Correct 3 ms 1280 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 ms 1280 KB Output is correct
5 Correct 3 ms 1280 KB Output is correct
6 Correct 3 ms 1280 KB Output is correct
7 Correct 22 ms 3968 KB Output is correct
8 Correct 23 ms 3968 KB Output is correct
9 Correct 23 ms 3840 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 ms 1280 KB Output is correct
5 Correct 3 ms 1280 KB Output is correct
6 Correct 3 ms 1280 KB Output is correct
7 Correct 22 ms 3968 KB Output is correct
8 Correct 23 ms 3968 KB Output is correct
9 Correct 23 ms 3840 KB Output is correct
10 Correct 251 ms 23160 KB Output is correct
11 Correct 259 ms 23036 KB Output is correct
12 Correct 117 ms 15644 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 3 ms 1280 KB Output is correct
5 Correct 3 ms 1280 KB Output is correct
6 Correct 3 ms 1280 KB Output is correct
7 Correct 22 ms 3968 KB Output is correct
8 Correct 23 ms 3968 KB Output is correct
9 Correct 23 ms 3840 KB Output is correct
10 Correct 251 ms 23160 KB Output is correct
11 Correct 259 ms 23036 KB Output is correct
12 Correct 117 ms 15644 KB Output is correct
13 Correct 2423 ms 140316 KB Output is correct
14 Correct 2416 ms 140628 KB Output is correct
15 Correct 2224 ms 133240 KB Output is correct