oj.uz

Submission #222285

# Submission time Handle Problem Language Result Execution time Memory
222285 2020-04-13T01:47:03 Z mathking1021 Quality Of Living (IOI10_quality) C++14
100 / 100
 3012 ms 246372 KB 
#include "quality.h"

typedef long long ll;

ll r, c, h, w;
ll a[3005][3005];
ll b[3005][3005];

bool f(ll p)
{
    for(ll i = 1; i <= r; i++)
    {
        for(ll j = 1; j <= c; j++)
        {
            if(a[i][j] <= p) b[i][j] = 1;
            else b[i][j] = 0;
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
        }
    }
    for(ll i = h; i <= r; i++)
    {
        for(ll j = w; j <= c; j++)
        {
            ll t = b[i][j] - b[i - h][j] - b[i][j - w] + b[i - h][j - w];
            if(t >= (h * w + 1) / 2) return true;
        }
    }
    return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    r = R;
    c = C;
    h = H;
    w = W;
    for(ll i = 0; i < r; i++)
    {
        for(ll j = 0; j < c; j++)
        {
            a[i + 1][j + 1] = Q[i][j];
        }
    }
    ll lt = 0, rt = r * c, mid, ans = 0;
    while(lt <= rt)
    {
        mid = (lt + rt) / 2;
        if(f(mid)) ans = mid, rt = mid - 1;
        else lt = mid + 1;
    }
    return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 7 ms 1792 KB Output is correct
5 Correct 7 ms 1792 KB Output is correct
6 Correct 7 ms 1792 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 7 ms 1792 KB Output is correct
5 Correct 7 ms 1792 KB Output is correct
6 Correct 7 ms 1792 KB Output is correct
7 Correct 29 ms 6272 KB Output is correct
8 Correct 30 ms 6272 KB Output is correct
9 Correct 27 ms 6000 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 7 ms 1792 KB Output is correct
5 Correct 7 ms 1792 KB Output is correct
6 Correct 7 ms 1792 KB Output is correct
7 Correct 29 ms 6272 KB Output is correct
8 Correct 30 ms 6272 KB Output is correct
9 Correct 27 ms 6000 KB Output is correct
10 Correct 346 ms 38704 KB Output is correct
11 Correct 321 ms 38648 KB Output is correct
12 Correct 161 ms 25464 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 7 ms 1792 KB Output is correct
5 Correct 7 ms 1792 KB Output is correct
6 Correct 7 ms 1792 KB Output is correct
7 Correct 29 ms 6272 KB Output is correct
8 Correct 30 ms 6272 KB Output is correct
9 Correct 27 ms 6000 KB Output is correct
10 Correct 346 ms 38704 KB Output is correct
11 Correct 321 ms 38648 KB Output is correct
12 Correct 161 ms 25464 KB Output is correct
13 Correct 3012 ms 246156 KB Output is correct
14 Correct 2920 ms 246372 KB Output is correct
15 Correct 2701 ms 239096 KB Output is correct