oj.uz

Submission #543498

# Submission time Handle Problem Language Result Execution time Memory
543498 2022-03-30T18:29:47 Z timreizin Quality Of Living (IOI10_quality) C++17
100 / 100
 2232 ms 165156 KB 
#include "quality.h"
#include <vector>

using namespace std;

bool check(int m, int h, int w, vector<vector<int>> &a)
{
    vector<vector<int>> pref = a;
    for (auto &i : pref) for (int &j : i) j = (j <= m ? -1 : 1);
    for (int i = 1; i < a.size(); ++i) for (int j = 0; j < a.front().size(); ++j) pref[i][j] += pref[i - 1][j];
    for (int i = 0; i < a.size(); ++i) for (int j = 1; j < a.front().size(); ++j) pref[i][j] += pref[i][j - 1];
    for (int i = 0; i + h - 1 < a.size(); ++i)
    {
        for (int j = 0; j + w - 1 < a.front().size(); ++j)
        {
            int sum = pref[i + h - 1][j + w - 1];
            if (i > 0) sum -= pref[i - 1][j + w - 1];
            if (j > 0) sum -= pref[i + h - 1][j - 1];
            if (i > 0 && j > 0) sum += pref[i - 1][j - 1];
            if (sum < 0) return true;
        }
    }
    return false;
}

int rectangle(int n, int m, int h, int w, int q[3001][3001])
{
    int l = 1, r = n * m;
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) a[i][j] = q[i][j];
    while (l < r)
    {
        int m = (l + r) >> 1;
        if (check(m, h, w, a)) r = m;
        else l = m + 1;
    }
    return l;
}

Compilation message

quality.cpp: In function 'bool check(int, int, int, std::vector<std::vector<int> >&)':
quality.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i = 1; i < a.size(); ++i) for (int j = 0; j < a.front().size(); ++j) pref[i][j] += pref[i - 1][j];
      |                     ~~^~~~~~~~~~
quality.cpp:10:58: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i = 1; i < a.size(); ++i) for (int j = 0; j < a.front().size(); ++j) pref[i][j] += pref[i - 1][j];
      |                                                        ~~^~~~~~~~~~~~~~~~~~
quality.cpp:11:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for (int i = 0; i < a.size(); ++i) for (int j = 1; j < a.front().size(); ++j) pref[i][j] += pref[i][j - 1];
      |                     ~~^~~~~~~~~~
quality.cpp:11:58: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for (int i = 0; i < a.size(); ++i) for (int j = 1; j < a.front().size(); ++j) pref[i][j] += pref[i][j - 1];
      |                                                        ~~^~~~~~~~~~~~~~~~~~
quality.cpp:12:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (int i = 0; i + h - 1 < a.size(); ++i)
      |                     ~~~~~~~~~~^~~~~~~~~~
quality.cpp:14:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |         for (int j = 0; j + w - 1 < a.front().size(); ++j)
      |                         ~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 2 ms 824 KB Output is correct
6 Correct 2 ms 816 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 2 ms 824 KB Output is correct
6 Correct 2 ms 816 KB Output is correct
7 Correct 17 ms 3116 KB Output is correct
8 Correct 18 ms 3088 KB Output is correct
9 Correct 15 ms 2932 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 2 ms 824 KB Output is correct
6 Correct 2 ms 816 KB Output is correct
7 Correct 17 ms 3116 KB Output is correct
8 Correct 18 ms 3088 KB Output is correct
9 Correct 15 ms 2932 KB Output is correct
10 Correct 207 ms 22836 KB Output is correct
11 Correct 207 ms 22860 KB Output is correct
12 Correct 111 ms 13620 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 2 ms 824 KB Output is correct
6 Correct 2 ms 816 KB Output is correct
7 Correct 17 ms 3116 KB Output is correct
8 Correct 18 ms 3088 KB Output is correct
9 Correct 15 ms 2932 KB Output is correct
10 Correct 207 ms 22836 KB Output is correct
11 Correct 207 ms 22860 KB Output is correct
12 Correct 111 ms 13620 KB Output is correct
13 Correct 2232 ms 164892 KB Output is correct
14 Correct 2089 ms 165156 KB Output is correct
15 Correct 1939 ms 152884 KB Output is correct