Submission #737896

# Submission time Handle Problem Language Result Execution time Memory
737896 2023-05-07T22:35:57 Z vjudge1 Quality Of Living (IOI10_quality) C++17
100 / 100
1561 ms 108904 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 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 564 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 564 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 2 ms 1224 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 564 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 2 ms 1224 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 14 ms 3912 KB Output is correct
8 Correct 14 ms 3936 KB Output is correct
9 Correct 15 ms 3788 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 564 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 2 ms 1224 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 14 ms 3912 KB Output is correct
8 Correct 14 ms 3936 KB Output is correct
9 Correct 15 ms 3788 KB Output is correct
10 Correct 174 ms 22808 KB Output is correct
11 Correct 164 ms 22968 KB Output is correct
12 Correct 110 ms 15436 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 564 KB Output is correct
4 Correct 3 ms 1236 KB Output is correct
5 Correct 2 ms 1224 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 14 ms 3912 KB Output is correct
8 Correct 14 ms 3936 KB Output is correct
9 Correct 15 ms 3788 KB Output is correct
10 Correct 174 ms 22808 KB Output is correct
11 Correct 164 ms 22968 KB Output is correct
12 Correct 110 ms 15436 KB Output is correct
13 Correct 1561 ms 108164 KB Output is correct
14 Correct 1510 ms 108904 KB Output is correct
15 Correct 1425 ms 101308 KB Output is correct