oj.uz

답안 #205423

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
205423 2020-02-28T22:55:27 Z jasony123123 삶의 질 (IOI10_quality) C++14
100 / 100
 2929 ms 140424 KB 
#include "quality.h"

#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define v vector
typedef long long ll;
typedef pair<int, int > pii;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

int _R, _C, _H, _W;
int T[3001][3001];

int get(int r1, int c1, int r2, int c2) {
	return T[r1][c1] - T[r2 + 1][c1] - T[r1][c2 + 1] + T[r2 + 1][c2 + 1];
}
bool test(int x, int Q[][3001]) {
	RFORE(r, _R - 1, 0)RFORE(c, _C - 1, 0) {
		T[r][c] = T[r + 1][c] + T[r][c + 1] - T[r + 1][c + 1];
		if (Q[r][c] < x) T[r][c]--;
		else if (Q[r][c] > x) T[r][c]++;
	}
	FOR(r, 0, _R - _H + 1)FOR(c, 0, _C - _W + 1)
		if (get(r, c, r + _H - 1, c + _W - 1) <= 0) return true;
	return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	_R = R, _C = C, _H = H, _W = W;
	int lo = 1, hi = R*C;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		if (test(mid, Q) == true) hi = mid;
		else lo = mid + 1;
	}
	return lo;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 632 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 7 ms 1272 KB Output is correct
5 Correct 7 ms 1272 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 7 ms 1272 KB Output is correct
5 Correct 7 ms 1272 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct
7 Correct 29 ms 4036 KB Output is correct
8 Correct 29 ms 3960 KB Output is correct
9 Correct 26 ms 3832 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 7 ms 1272 KB Output is correct
5 Correct 7 ms 1272 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct
7 Correct 29 ms 4036 KB Output is correct
8 Correct 29 ms 3960 KB Output is correct
9 Correct 26 ms 3832 KB Output is correct
10 Correct 313 ms 23008 KB Output is correct
11 Correct 299 ms 22904 KB Output is correct
12 Correct 162 ms 15736 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 7 ms 1272 KB Output is correct
5 Correct 7 ms 1272 KB Output is correct
6 Correct 7 ms 1272 KB Output is correct
7 Correct 29 ms 4036 KB Output is correct
8 Correct 29 ms 3960 KB Output is correct
9 Correct 26 ms 3832 KB Output is correct
10 Correct 313 ms 23008 KB Output is correct
11 Correct 299 ms 22904 KB Output is correct
12 Correct 162 ms 15736 KB Output is correct
13 Correct 2929 ms 140424 KB Output is correct
14 Correct 2900 ms 140288 KB Output is correct
15 Correct 2669 ms 133360 KB Output is correct