oj.uz

Submission #998231

# Submission time Handle Problem Language Result Execution time Memory
998231 2024-06-13T12:11:16 Z rahidilbayramli Quality Of Living (IOI10_quality) C++17
100 / 100
 1263 ms 105708 KB 
#include<bits/stdc++.h>
#include "quality.h"
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define f first
#define s second
#define pb push_back
#define p_b pop_back
using namespace std;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int l = 1, r = R * C, ans = R * C;
	while(l <= r)
    {
        int grid[3001][3001];
        int mid = (l + r) / 2, maxx = 0;
        for(int i = 0; i < R; i++)
        {
            for(int j = 0; j < C; j++)
            {
                int sum = 0;
                grid[i][j] = (Q[i][j] <= mid);
                if(i)
                    grid[i][j] += grid[i-1][j];
                if(j)
                    grid[i][j] += grid[i][j-1];
                if(i && j)
                    grid[i][j] -= grid[i-1][j-1];
                sum = grid[i][j];
                if(i - H >= 0)
                    sum -= grid[i-H][j];
                if(j - W >= 0)
                    sum -= grid[i][j-W];
                if(i - H >= 0 && j - W >= 0)
                    sum += grid[i-H][j-W];
                maxx = max(maxx, sum);
            }
        }
        if(maxx > H * W / 2)
        {
            ans = min(ans, mid);
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37720 KB Output is correct
2 Correct 18 ms 37724 KB Output is correct
3 Correct 21 ms 37720 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37720 KB Output is correct
2 Correct 18 ms 37724 KB Output is correct
3 Correct 21 ms 37720 KB Output is correct
4 Correct 25 ms 37652 KB Output is correct
5 Correct 19 ms 37720 KB Output is correct
6 Correct 19 ms 37712 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37720 KB Output is correct
2 Correct 18 ms 37724 KB Output is correct
3 Correct 21 ms 37720 KB Output is correct
4 Correct 25 ms 37652 KB Output is correct
5 Correct 19 ms 37720 KB Output is correct
6 Correct 19 ms 37712 KB Output is correct
7 Correct 29 ms 40272 KB Output is correct
8 Correct 29 ms 40284 KB Output is correct
9 Correct 27 ms 40144 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37720 KB Output is correct
2 Correct 18 ms 37724 KB Output is correct
3 Correct 21 ms 37720 KB Output is correct
4 Correct 25 ms 37652 KB Output is correct
5 Correct 19 ms 37720 KB Output is correct
6 Correct 19 ms 37712 KB Output is correct
7 Correct 29 ms 40272 KB Output is correct
8 Correct 29 ms 40284 KB Output is correct
9 Correct 27 ms 40144 KB Output is correct
10 Correct 143 ms 51536 KB Output is correct
11 Correct 144 ms 51544 KB Output is correct
12 Correct 78 ms 49744 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 37720 KB Output is correct
2 Correct 18 ms 37724 KB Output is correct
3 Correct 21 ms 37720 KB Output is correct
4 Correct 25 ms 37652 KB Output is correct
5 Correct 19 ms 37720 KB Output is correct
6 Correct 19 ms 37712 KB Output is correct
7 Correct 29 ms 40272 KB Output is correct
8 Correct 29 ms 40284 KB Output is correct
9 Correct 27 ms 40144 KB Output is correct
10 Correct 143 ms 51536 KB Output is correct
11 Correct 144 ms 51544 KB Output is correct
12 Correct 78 ms 49744 KB Output is correct
13 Correct 1244 ms 105708 KB Output is correct
14 Correct 1263 ms 105680 KB Output is correct
15 Correct 1182 ms 101964 KB Output is correct