Submission #543498

#	Time	Username	Problem	Language	Result	Execution time	Memory
543498		timreizin	Quality Of Living (IOI10_quality)	C++17	100 / 100	2232 ms	165156 KiB

quality

#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 (stderr)

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20