oj.uz

Submission #208958

# Submission time Handle Problem Language Result Execution time Memory
208958 2020-03-12T19:07:46 Z 2Nor22 Quality Of Living (IOI10_quality) C++14
100 / 100
 2952 ms 176984 KB 
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <cstdint>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <tuple>
#include <list>
#include <set>
#include <map>
#define add push_back
#define m_p make_pair
#define fr first
#define sc second
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef long double ld;
typedef pair<ll, ll> pii;
const ll N = 1000005, mod = 998244353, M = 3001;
ll n, m, k, i, j, ans, kaskad[N], matrix[M][M], pref[M][M], h, w;
bool check(ll value)
{
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			ll x = -1;
			if (matrix[i][j] > value)
				x = 1;
			else if (matrix[i][j] == value)
				x = 0;
			pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + x;
		}
	}
	for (int i = h; i <= n; ++i)
	{
		for (int j = w; j <= m; ++j)
		{
			if (pref[i][j] - pref[i - h][j] - pref[i][j - w] + pref[i - h][j - w] <= 0)
				return true;
		}
	}
	return false;
}
void BinarySearch(ll left, ll right)
{
	if (right - left <= 1)
		return;
	ll mid = (left + right) / 2;
	if (!check(mid))
	{
		BinarySearch(mid, right);
	}
	else
	{
		ans = mid;
		BinarySearch(left, mid);
	}
}
int rectangle(int nn, int mm, int hh, int ww, int a[M][M])
{
	n = nn;
	m = mm;
	h = hh;
	w = ww;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			matrix[i + 1][j + 1] = a[i][j];
		}
	}
	BinarySearch(0, n * m);
	return ans;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 7 ms 1784 KB Output is correct
5 Correct 8 ms 1784 KB Output is correct
6 Correct 8 ms 1784 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 7 ms 1784 KB Output is correct
5 Correct 8 ms 1784 KB Output is correct
6 Correct 8 ms 1784 KB Output is correct
7 Correct 31 ms 6264 KB Output is correct
8 Correct 30 ms 6264 KB Output is correct
9 Correct 28 ms 6008 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 7 ms 1784 KB Output is correct
5 Correct 8 ms 1784 KB Output is correct
6 Correct 8 ms 1784 KB Output is correct
7 Correct 31 ms 6264 KB Output is correct
8 Correct 30 ms 6264 KB Output is correct
9 Correct 28 ms 6008 KB Output is correct
10 Correct 314 ms 34940 KB Output is correct
11 Correct 302 ms 34936 KB Output is correct
12 Correct 160 ms 25084 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 7 ms 1784 KB Output is correct
5 Correct 8 ms 1784 KB Output is correct
6 Correct 8 ms 1784 KB Output is correct
7 Correct 31 ms 6264 KB Output is correct
8 Correct 30 ms 6264 KB Output is correct
9 Correct 28 ms 6008 KB Output is correct
10 Correct 314 ms 34940 KB Output is correct
11 Correct 302 ms 34936 KB Output is correct
12 Correct 160 ms 25084 KB Output is correct
13 Correct 2952 ms 176800 KB Output is correct
14 Correct 2871 ms 176984 KB Output is correct
15 Correct 2636 ms 176760 KB Output is correct