Submission #737897

# Submission time Handle Problem Language Result Execution time Memory
737897 2023-05-07T22:38:26 Z boyliguanhan Quality Of Living (IOI10_quality) C++17
100 / 100
1472 ms 70972 KB
#include "quality.h"
#include<bits/stdc++.h>
#include<bits/extc++.h>
#pragma GCC optimize(2)
using namespace std;
using namespace __gnu_pbds;
#define P(x) pair<x,x>
#define TP(x) tuple<x,x,x>
#define V vector
#define F first
#define S second
#define TT get<2>
#define TS get<1>
#define TF get<0>
#define LE less_equal
#define GE greater_equal
#define all(x) x.begin(), x.end()
#define For(i,s,n) for(int i = s; i < n; i++)
#define Rfor(i,s,n) for(int i = n; i>=s; i--)
#define ForR(i,v) for(auto i:v)
//#define int long long // might cause errors if problem is ioi style
#define ll long long // replacement for above if problem is ioi style
#define PB push_back
#define bll __int128_t //warning: not possible to IO a bll
#define ubll __uint128_t // IO doesn't work for ubll too
#define US unsigned
#define rbt tb_tree_tag
#define splt splay_tree_tag
#define avlt ov_tree_tag
#define Tree(t, cp, tg) tree<t, null_type, cp<i>, tg, tree_order_statistics_node_update>
#define PQ priority_queue
#define GR greater
#define rch(x) x = getchar_unlocked()
#define inf ((ll)(1e18))
#define mod ((int)(1e9+7))
#define db double
#define ldb long double
#define MXN 200100 //change this value according to problem
#define MXM 200100 //change this too
int p[3001][3001];
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int l = 1, r = R*C;
	while(l<r) {
		int mid = l + r >> 1;
		bool ans = 0;
		For(i,1,R+1)For(j,1,C+1)p[i][j] = p[i][j-1]+p[i-1][j]-p[i-1][j-1]+(Q[i-1][j-1]>mid);
		For(i,H,R+1)For(j,W,C+1)ans|=(p[i][j]-p[i-H][j]-p[i][j-W]+p[i-H][j-W] <= H*W/2);
		if(ans) {
			r = mid;
		} else {
			l = mid + 1;
		}
	}
	return l;
}

Compilation message

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:44:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |   int mid = l + r >> 1;
      |             ~~^~~
# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 1108 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 1108 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 15 ms 3428 KB Output is correct
8 Correct 15 ms 3416 KB Output is correct
9 Correct 12 ms 3284 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 1108 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 15 ms 3428 KB Output is correct
8 Correct 15 ms 3416 KB Output is correct
9 Correct 12 ms 3284 KB Output is correct
10 Correct 172 ms 16128 KB Output is correct
11 Correct 155 ms 16032 KB Output is correct
12 Correct 84 ms 12176 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 1108 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1108 KB Output is correct
7 Correct 15 ms 3428 KB Output is correct
8 Correct 15 ms 3416 KB Output is correct
9 Correct 12 ms 3284 KB Output is correct
10 Correct 172 ms 16128 KB Output is correct
11 Correct 155 ms 16032 KB Output is correct
12 Correct 84 ms 12176 KB Output is correct
13 Correct 1472 ms 70788 KB Output is correct
14 Correct 1431 ms 70732 KB Output is correct
15 Correct 1346 ms 70972 KB Output is correct