oj.uz

답안 #761100

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
761100 2023-06-19T07:50:35 Z Blagoj 삶의 질 (IOI10_quality) C++17
100 / 100
 2764 ms 210788 KB 
#include <bits/stdc++.h>
#include "quality.h"

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()

int h, w, r, c, a[3002][3002], dp[3002][3002];

bool b(int v) {
    int s = (h * w) / 2 + 1;
    for (int i = 0; i < r; i++) {
        int cnt = 0;
        for (int j = 0; j < c; j++) {
            if (a[i][j] <= v) cnt++;
            dp[i][j] = cnt;
            if (i - 1 >= 0) {
                dp[i][j] += dp[i - 1][j];
            }
            if (i == h - 1 && j == w - 1) {
                if (dp[i][j] >= s) return 1;
            }
            else if (i == h - 1 && j >= w) {
                if (dp[i][j] - dp[i][j - w] >= s) return 1;
            }
            else if (i >= h && j == w - 1) {
                if (dp[i][j] - dp[i - h][j] >= s) return 1;
            }
            else if (i >= h - 1 && j >= w - 1) {
                if (dp[i][j] - dp[i - h][j] - dp[i][j - w] + dp[i - h][j - w] >= s) return 1;
            }
        }
    }
    return 0;
}

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 = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            a[i][j] = Q[i][j];
        }
    }
    vector<int> v;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> a[i][j];
            v.push_back(a[i][j]);
        }
    }
    int l = 0, rr = r * c;
    sort(all(v));
    int ans = INT_MAX;
    while (l + 1 < rr) {
        int m = (l + rr) / 2;
        if (b(v[m])) {
            ans = min(ans, v[m]);
            rr = m;
        }
        else {
            l = m;
        }
    }
    if (b(v[0])) ans = v[0];
    return ans;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 692 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 692 KB Output is correct
4 Correct 3 ms 1748 KB Output is correct
5 Correct 3 ms 1724 KB Output is correct
6 Correct 3 ms 1728 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 692 KB Output is correct
4 Correct 3 ms 1748 KB Output is correct
5 Correct 3 ms 1724 KB Output is correct
6 Correct 3 ms 1728 KB Output is correct
7 Correct 22 ms 5988 KB Output is correct
8 Correct 23 ms 5996 KB Output is correct
9 Correct 23 ms 5700 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 692 KB Output is correct
4 Correct 3 ms 1748 KB Output is correct
5 Correct 3 ms 1724 KB Output is correct
6 Correct 3 ms 1728 KB Output is correct
7 Correct 22 ms 5988 KB Output is correct
8 Correct 23 ms 5996 KB Output is correct
9 Correct 23 ms 5700 KB Output is correct
10 Correct 270 ms 34736 KB Output is correct
11 Correct 270 ms 34816 KB Output is correct
12 Correct 131 ms 23480 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 692 KB Output is correct
4 Correct 3 ms 1748 KB Output is correct
5 Correct 3 ms 1724 KB Output is correct
6 Correct 3 ms 1728 KB Output is correct
7 Correct 22 ms 5988 KB Output is correct
8 Correct 23 ms 5996 KB Output is correct
9 Correct 23 ms 5700 KB Output is correct
10 Correct 270 ms 34736 KB Output is correct
11 Correct 270 ms 34816 KB Output is correct
12 Correct 131 ms 23480 KB Output is correct
13 Correct 2701 ms 210788 KB Output is correct
14 Correct 2764 ms 210736 KB Output is correct
15 Correct 2405 ms 200112 KB Output is correct