이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//control+option+n to run!
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define FOR(i, a, b) for (signed long long i = (signed long long)(a); i < (signed long long)(b); i++)
#define NEGFOR(i, a, b) for (ll i = (a); i > (b); i--)
#define vll vector<long long>
#define sll set<long long>
#define ld long double
#define inf 1000000000000000000
#define mll multiset<long long>
#define vpll vector<pll>
#define nn << "\n"
#define ss << " "
#define F(i, b) for (ll i = 0; i < b; i++)
//10^8 operations per second
//greatest int is 2,147,483,647
//greates long long is 9.22337204e18
//ALL FUNCTIONS SHOULD BE LL!!!!
ll power(ll x, ll n, ll m)
{
assert(n >= 0);
x %= m; //note: m*m must be less than 2^63 to avoid ll overflow
ll res = 1;
while (n > 0)
{
if (n % 2 == 1) //if n is odd
res = res * x % m;
x = x * x % m;
n /= 2; //divide by two
}
return res;
}
ll log(ll base, ll number)
{
int x = base;
int count = 1;
while (base < number)
{
base *= x;
count++;
}
return count;
}
bool check(int val, int r, int c, int h, int w, int p[3001][3001]){
FOR(i,0,r){
FOR(j,0,c){
if (p[i][j]>val)
p[i][j]=-1;
else if (p[i][j]<val){
p[i][j]=1;
}
else{
p[i][j]=0;
}
}
}
int prefix[3002][3002];
FOR(i,0,3002){
prefix[i][0]=0;
prefix[0][i]=0;
}
FOR(i,1,r+1){
FOR(j,1,c+1){
prefix[i][j]=p[i][j]-prefix[i-1][j-1]+prefix[i][j-1]+prefix[i-1][j];
}
}
for (int i = h; i <= r; i++)
for (int j = w; j <= c; j++)
if (prefix[i][j] - prefix[i - h][j] - prefix[i][j - w] + prefix[i - h][j - w] > h * w / 2) return true;
return false;
}
int rectangle(int r, int c, int h, int w, int p[3001][3001])
{
int le=1, ri=1e8;
while(check(ri,r,c,h,w,p)){
int mid= le+(ri-le)/2;
if (!check(mid,r,c,h,w,p)){
le=mid+1;
}
else{
ri=mid-1;
}
}
return --le;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |