oj.uz

Submission #411434

# Submission time Handle Problem Language Result Execution time Memory
411434 2021-05-25T10:11:28 Z alextodoran Quality Of Living (IOI10_quality) C++17
100 / 100
 2045 ms 155948 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>
#include "quality.h"

using namespace std;

typedef long long ll;

const int NM_MAX = 3000;

int n, m;

int r, c;

int mat[NM_MAX + 2][NM_MAX + 2];

int sum[NM_MAX + 2][NM_MAX + 2];

bool solve (int lwr)
{
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            sum[i][j] = (mat[i][j] < lwr) + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
    for(int i = r; i <= n; i++)
        for(int j = c; j <= m; j++)
        {
            int in = sum[i][j] - sum[i - r][j] - sum[i][j - c] + sum[i - r][j - c];
            if(in <= r * c / 2)
                return true;
        }
    return false;
}

int rectangle (int N, int M, int R, int C, int Q[NM_MAX + 1][NM_MAX + 1])
{
    n = N;
    m = M;
    r = R;
    c = C;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            mat[i][j] = n * m - Q[i - 1][j - 1] + 1;
    int l = 1, r = n * m;
    while(l < r)
    {
        int mid = (l + r + 1) / 2;
        if(solve(mid) == true)
            l = mid;
        else
            r = mid - 1;
    }
    return n * m - l + 1;
}

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 2 ms 684 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 2 ms 684 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 2 ms 684 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 18 ms 5516 KB Output is correct
8 Correct 20 ms 5516 KB Output is correct
9 Correct 21 ms 5324 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 2 ms 684 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 18 ms 5516 KB Output is correct
8 Correct 20 ms 5516 KB Output is correct
9 Correct 21 ms 5324 KB Output is correct
10 Correct 207 ms 30860 KB Output is correct
11 Correct 205 ms 30732 KB Output is correct
12 Correct 124 ms 21480 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 2 ms 684 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 18 ms 5516 KB Output is correct
8 Correct 20 ms 5516 KB Output is correct
9 Correct 21 ms 5324 KB Output is correct
10 Correct 207 ms 30860 KB Output is correct
11 Correct 205 ms 30732 KB Output is correct
12 Correct 124 ms 21480 KB Output is correct
13 Correct 2045 ms 155948 KB Output is correct
14 Correct 1900 ms 155936 KB Output is correct
15 Correct 1878 ms 151776 KB Output is correct