oj.uz

Submission #861845

# Submission time Handle Problem Language Result Execution time Memory
861845 2023-10-17T04:21:28 Z sleepntsheep Quality Of Living (IOI10_quality) C++17
100 / 100
 1453 ms 178712 KB 
#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll=long long;

#define ALL(x) x.begin(), x.end()
#define N 3086

int n, m, h, w, a[N][N], p[N][N];

int ok(int y)
{
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) p[i][j] = (a[i][j] <= y) + p[i-1][j] + p[i][j-1] - p[i-1][j-1];
    for (int i = 1; i + h - 1 <= n; ++i) for (int j = 1; j + w - 1 <= m; ++j)
        if (p[i+h-1][j+w-1] - p[i-1][j+w-1] - p[i+h-1][j-1] + p[i-1][j-1] > (h*w-1)/2) return 1;
    return 0;
}

int rectangle(int n, int m, int h, int w, int q[3001][3001])
{
    ::n=n,::m=m,::h=h,::w=w;
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) a[i][j] = q[i-1][j-1];
    
    int l = 0, r = 1e9;
    while (l <= r)
    {
        int y = (l+r)/2;
        ok(y) ? r = y - 1 : l = y + 1;
    }
    return r+1;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4848 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4848 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 15 ms 10588 KB Output is correct
8 Correct 15 ms 10588 KB Output is correct
9 Correct 16 ms 10584 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4848 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 15 ms 10588 KB Output is correct
8 Correct 15 ms 10588 KB Output is correct
9 Correct 16 ms 10584 KB Output is correct
10 Correct 164 ms 40536 KB Output is correct
11 Correct 160 ms 40532 KB Output is correct
12 Correct 83 ms 34344 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4848 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 15 ms 10588 KB Output is correct
8 Correct 15 ms 10588 KB Output is correct
9 Correct 16 ms 10584 KB Output is correct
10 Correct 164 ms 40536 KB Output is correct
11 Correct 160 ms 40532 KB Output is correct
12 Correct 83 ms 34344 KB Output is correct
13 Correct 1453 ms 178712 KB Output is correct
14 Correct 1390 ms 178516 KB Output is correct
15 Correct 1333 ms 171616 KB Output is correct