oj.uz

Submission #492094

# Submission time Handle Problem Language Result Execution time Memory
492094 2021-12-05T11:53:40 Z Alexandruabcde Quality Of Living (IOI10_quality) C++14
100 / 100
 1674 ms 210816 KB 
#include "quality.h"
#include <bits/stdc++.h>
#define ub(x) (x&(-x))

using namespace std;

constexpr int NMAX = 3005;
int N, M, X, Y;
int mat[NMAX][NMAX];

int mare[NMAX][NMAX];
int mic[NMAX][NMAX];

bool Check (int val) {
    for (int i = 1; i <= N; ++ i )
        for (int j = 1; j <= M; ++ j ) {
            mare[i][j] = mare[i-1][j] + mare[i][j-1] - mare[i-1][j-1] + (mat[i][j] > val);
            mic[i][j] = mic[i-1][j] + mic[i][j-1] - mic[i-1][j-1] + (mat[i][j] < val);
        }

    for (int i = X; i <= N; ++ i ) {
        for (int j = Y; j <= M; ++ j ) {
            int cntMare = mare[i][j] - mare[i-X][j] - mare[i][j-Y] + mare[i-X][j-Y];
            int cntMic = mic[i][j] - mic[i-X][j] - mic[i][j-Y] + mic[i-X][j-Y];

            if (cntMic >= cntMare) return 1;
        }
    }

    return 0;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    N = R, M = C, X = H, Y = W;

    for (int i = 1; i <= N; ++ i )
        for (int j = 1; j <= M; ++ j )
            mat[i][j] = Q[i-1][j-1];

    int st = 1, dr = R * C + 1;
    int ans = 0;

    while (st <= dr) {
        int mij = (st + dr) / 2;

        if (Check(mij)) {
            dr = mij-1;
            ans = mij;
        }
        else st = mij + 1;
    }

    return ans;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 2 ms 2124 KB Output is correct
5 Correct 4 ms 1996 KB Output is correct
6 Correct 2 ms 1996 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 2 ms 2124 KB Output is correct
5 Correct 4 ms 1996 KB Output is correct
6 Correct 2 ms 1996 KB Output is correct
7 Correct 18 ms 6972 KB Output is correct
8 Correct 20 ms 7040 KB Output is correct
9 Correct 16 ms 6772 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 2 ms 2124 KB Output is correct
5 Correct 4 ms 1996 KB Output is correct
6 Correct 2 ms 1996 KB Output is correct
7 Correct 18 ms 6972 KB Output is correct
8 Correct 20 ms 7040 KB Output is correct
9 Correct 16 ms 6772 KB Output is correct
10 Correct 193 ms 38728 KB Output is correct
11 Correct 173 ms 38616 KB Output is correct
12 Correct 95 ms 27464 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 716 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 2 ms 2124 KB Output is correct
5 Correct 4 ms 1996 KB Output is correct
6 Correct 2 ms 1996 KB Output is correct
7 Correct 18 ms 6972 KB Output is correct
8 Correct 20 ms 7040 KB Output is correct
9 Correct 16 ms 6772 KB Output is correct
10 Correct 193 ms 38728 KB Output is correct
11 Correct 173 ms 38616 KB Output is correct
12 Correct 95 ms 27464 KB Output is correct
13 Correct 1642 ms 210816 KB Output is correct
14 Correct 1674 ms 210748 KB Output is correct
15 Correct 1520 ms 203696 KB Output is correct