oj.uz

답안 #594849

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
594849 2022-07-13T04:37:19 Z skittles1412 삶의 질 (IOI10_quality) C++17
100 / 100
 2117 ms 175348 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

int rectangle(int n, int m, int qn, int qm, int arr[3001][3001]) {
    vector<int> aarr;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            aarr.push_back(arr[i][j]);
        }
    }
    sort(begin(aarr), end(aarr));
    auto check = [&](int x) -> bool {
        int psums[n + 1][m + 1] {};
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                psums[i + 1][j + 1] = psums[i + 1][j] + psums[i][j + 1] -
                                      psums[i][j] + (arr[i][j] <= aarr[x]);
            }
        }
        int targ = qn * qm / 2;
        for (int i = 0; i + qn <= n; i++) {
            for (int j = 0; j + qm <= m; j++) {
                int x1 = i, x2 = i + qn, y1 = j, y2 = j + qm;
                if (psums[x2][y2] - psums[x1][y2] - psums[x2][y1] +
                        psums[x1][y1] >
                    targ) {
                    if (aarr[x] == 8) {
                        dbg(i, j);
                    }
                    return true;
                }
            }
        }
        return false;
    };
    int l = 0, r = sz(aarr) - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return aarr[l];
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 2 ms 900 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 828 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 2 ms 900 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 828 KB Output is correct
7 Correct 18 ms 3124 KB Output is correct
8 Correct 24 ms 3148 KB Output is correct
9 Correct 17 ms 3068 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 2 ms 900 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 828 KB Output is correct
7 Correct 18 ms 3124 KB Output is correct
8 Correct 24 ms 3148 KB Output is correct
9 Correct 17 ms 3068 KB Output is correct
10 Correct 205 ms 22956 KB Output is correct
11 Correct 226 ms 22844 KB Output is correct
12 Correct 112 ms 13600 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 2 ms 900 KB Output is correct
5 Correct 2 ms 852 KB Output is correct
6 Correct 2 ms 828 KB Output is correct
7 Correct 18 ms 3124 KB Output is correct
8 Correct 24 ms 3148 KB Output is correct
9 Correct 17 ms 3068 KB Output is correct
10 Correct 205 ms 22956 KB Output is correct
11 Correct 226 ms 22844 KB Output is correct
12 Correct 112 ms 13600 KB Output is correct
13 Correct 2117 ms 175320 KB Output is correct
14 Correct 2013 ms 175348 KB Output is correct
15 Correct 1915 ms 161148 KB Output is correct