oj.uz

Submission #735306

# Submission time Handle Problem Language Result Execution time Memory
735306 2023-05-03T23:57:51 Z That_Salamander Quality Of Living (IOI10_quality) C++17
100 / 100
 1283 ms 89324 KB 
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <set>

#define FOR(var,bound) for(int var = 0; var < bound; var++)
#define FORB(var,lb,ub) for (int var = lb; var < ub; var++)
#define FORR(var,bound) for(int var = bound-1; var >= 0; var--)

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

int p[3001][3001];

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    int l = 1;
    int r = R * C + 1;
    int target = (H * W + 1) / 2;

    while (l != r - 1) {
        int mid = (l + r) / 2;

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                p[i+1][j+1] = (Q[i][j] <= mid) + p[i][j+1] + p[i+1][j] - p[i][j];
            }
        }

        bool valid = false;

        for (int i = 0; i + H <= R && !valid; i++) {
            for (int j = 0; j + W <= C; j++) {
                if (p[i+H][j+W] - p[i+H][j] - p[i][j+W] + p[i][j] >= target) {
                    valid = true;
                    break;
                }
            }
        }

        if (valid) {
            r = mid;
        } else {
            l = mid;
        }
    }

    return r;
}

#ifdef LOCAL_TEST
int grid[3001][3001];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int r, c, h, w;
    cin >> r >> c >> h >> w;


    FOR(i, r) {
        FOR(j, c) {
            cin >> grid[i][j];
        }
    }

    cout << rectangle(r, c, h, w, grid) << endl;
}
#endif

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 564 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1212 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 564 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1212 KB Output is correct
7 Correct 13 ms 3968 KB Output is correct
8 Correct 14 ms 3944 KB Output is correct
9 Correct 11 ms 3776 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 564 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1212 KB Output is correct
7 Correct 13 ms 3968 KB Output is correct
8 Correct 14 ms 3944 KB Output is correct
9 Correct 11 ms 3776 KB Output is correct
10 Correct 168 ms 22860 KB Output is correct
11 Correct 128 ms 22760 KB Output is correct
12 Correct 69 ms 15560 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 564 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 1236 KB Output is correct
5 Correct 2 ms 1108 KB Output is correct
6 Correct 2 ms 1212 KB Output is correct
7 Correct 13 ms 3968 KB Output is correct
8 Correct 14 ms 3944 KB Output is correct
9 Correct 11 ms 3776 KB Output is correct
10 Correct 168 ms 22860 KB Output is correct
11 Correct 128 ms 22760 KB Output is correct
12 Correct 69 ms 15560 KB Output is correct
13 Correct 1283 ms 89324 KB Output is correct
14 Correct 1195 ms 87920 KB Output is correct
15 Correct 1185 ms 87352 KB Output is correct