Submission #321143

#	Time	Username	Problem	Language	Result	Execution time	Memory
321143		daringtrifles	Quality Of Living (IOI10_quality)	C++17	0 / 100	9 ms	12524 KiB

quality

//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;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20