oj.uz

Submission #211926

# Submission time Handle Problem Language Result Execution time Memory
211926 2020-03-21T18:15:38 Z mode149256 Quality Of Living (IOI10_quality) C++14
100 / 100
 2769 ms 140636 KB 
#include <bits/stdc++.h>
#include "quality.h"
using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {

	auto gali = [&](int m) -> bool {
		vii sk(R, vi(C, 0));

		int reik = H * W / 2 + 1;

		for (int i = 0; i < R; ++i)
		{
			for (int j = 0; j < C; ++j)
			{
				sk[i][j] = int(Q[i][j] <= m);
				if (i) sk[i][j] += sk[i - 1][j];
				if (j) sk[i][j] += sk[i][j - 1];
				if (i and j) sk[i][j] -= sk[i - 1][j - 1];

				if (i >= H - 1 and j >= W - 1) {
					int dab = sk[i][j];
					if (i - H >= 0) dab -= sk[i - H][j];
					if (j - W >= 0) dab -= sk[i][j - W];
					if (i - H >= 0 and j - W >= 0)	dab += sk[i - H][j - W];

					// printf("m = %d, i = %d, j = %d, dab = %d, sk = %d\n",
					// m, i, j, dab, sk[i][j]);
					if (dab >= reik) return true;
				}
			}
		}

		return false;
	};

	int l = 1;
	int h = R * C;
	int m;
	while (l < h) {
		m = (l + h) / 2;
		// printf("l = %d, m = %d, h = %d, gali = %d\n", l, m, h, (int)gali(m));
		if (gali(m))
			h = m;
		else
			l = m + 1;
	}
	return l;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 6 ms 896 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 25 ms 2868 KB Output is correct
8 Correct 25 ms 2848 KB Output is correct
9 Correct 23 ms 2748 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 25 ms 2868 KB Output is correct
8 Correct 25 ms 2848 KB Output is correct
9 Correct 23 ms 2748 KB Output is correct
10 Correct 280 ms 19036 KB Output is correct
11 Correct 277 ms 19060 KB Output is correct
12 Correct 129 ms 11732 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 25 ms 2868 KB Output is correct
8 Correct 25 ms 2848 KB Output is correct
9 Correct 23 ms 2748 KB Output is correct
10 Correct 280 ms 19036 KB Output is correct
11 Correct 277 ms 19060 KB Output is correct
12 Correct 129 ms 11732 KB Output is correct
13 Correct 2769 ms 140636 KB Output is correct
14 Correct 2710 ms 140468 KB Output is correct
15 Correct 2464 ms 130064 KB Output is correct