oj.uz

Submission #797303

# Submission time Handle Problem Language Result Execution time Memory
797303 2023-07-29T09:00:48 Z makanhulia Quality Of Living (IOI10_quality) C++17
100 / 100
 1665 ms 175236 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 688 KB Output is correct
3 Correct 1 ms 596 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 688 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 3 ms 1620 KB Output is correct
5 Correct 3 ms 1584 KB Output is correct
6 Correct 3 ms 1620 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 688 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 3 ms 1620 KB Output is correct
5 Correct 3 ms 1584 KB Output is correct
6 Correct 3 ms 1620 KB Output is correct
7 Correct 15 ms 5436 KB Output is correct
8 Correct 16 ms 5460 KB Output is correct
9 Correct 13 ms 5332 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 688 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 3 ms 1620 KB Output is correct
5 Correct 3 ms 1584 KB Output is correct
6 Correct 3 ms 1620 KB Output is correct
7 Correct 15 ms 5436 KB Output is correct
8 Correct 16 ms 5460 KB Output is correct
9 Correct 13 ms 5332 KB Output is correct
10 Correct 168 ms 30692 KB Output is correct
11 Correct 172 ms 30772 KB Output is correct
12 Correct 84 ms 21452 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 688 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 3 ms 1620 KB Output is correct
5 Correct 3 ms 1584 KB Output is correct
6 Correct 3 ms 1620 KB Output is correct
7 Correct 15 ms 5436 KB Output is correct
8 Correct 16 ms 5460 KB Output is correct
9 Correct 13 ms 5332 KB Output is correct
10 Correct 168 ms 30692 KB Output is correct
11 Correct 172 ms 30772 KB Output is correct
12 Correct 84 ms 21452 KB Output is correct
13 Correct 1665 ms 175236 KB Output is correct
14 Correct 1621 ms 175236 KB Output is correct
15 Correct 1491 ms 168216 KB Output is correct