Submission #797303

#	Time	Username	Problem	Language	Result	Execution time	Memory
797303		makanhulia	Quality Of Living (IOI10_quality)	C++17	100 / 100	1665 ms	175236 KiB

quality

#include<bits/stdc++.h>
#include "quality.h"
#define ll long long
#define pb push_back
using namespace std;

int h , w , r , c , grid[3001][3001] , pref[3001][3001];

void reset(){
    for(int i = 0 ; i <= r ; i++){
        for(int j = 0 ; j <= c ; j++){
            pref[i][j] = 0;
        }
    }
}

bool inside(int x , int y){
    return 0 < x && x <= r && 0 < y && y <= c;
}

int rectangle(int R , int C , int H , int W , int Q[3001][3001]){
    r = R; c = C; h = H; w = W;
    for(int i = 1 ; i <= r ; i++){
        for(int j = 1 ; j <= c ; j++){
            grid[i][j] = Q[i - 1][j - 1];
        }
    }
    int lef = 0 , rig = r * c , ans = 0;
    while(lef <= rig){
        int mid = (lef + rig) / 2;
        reset();
        for(int i = 1 ; i <= r ; i++){
            for(int j = 1 ; j <= c ; j++){
                pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + (grid[i][j] <= mid);
            }
        }
        bool bs = false;
        for(int i = 1 ; i <= r ; i++){
            for(int j = 1 ; j <= c ; j++){
                int x = i , y = j , x0 = x + h - 1 , y0 = y + w - 1;
                if(inside(x0 , y0)){
                    int tt = pref[x0][y0] - pref[x - 1][y0] - pref[x0][y - 1] + pref[x - 1][y - 1];
                    //cout << x << " " << y << " " << x0 << " " << y0 << " " << pref[x0][y0] << " " << pref[x][y0] << " " << pref[x0][y] << " " << pref[x][y] << endl;
                    if(tt > (h * w) / 2) bs = true;
                }
            }
        }
        if(bs){
            ans = mid;
            rig = mid - 1;
        }
        else{
            lef = mid + 1;
        }
    }
    return ans;
}

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