oj.uz

답안 #401984

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
401984 2021-05-11T06:10:52 Z IloveN 삶의 질 (IOI10_quality) C++14
100 / 100
 2085 ms 140284 KB 
#include<bits/stdc++.h>
#include "quality.h"

using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
const int N = 3e3 + 10;

int ps[N][N];

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int l = 1, r = R * C, ans = 0;
	while (l <= r)
    {
        int mid = (l + r) / 2;
        for (int i = 1; i <= R; ++i)
            for (int j = 1; j <= C; ++j)
                ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + (Q[i - 1][j - 1] <= mid);
        int mx = 0;
        for (int i = 1; i <= R - H + 1; ++i)
            for (int j = 1; j <= C - W + 1; ++j)
                mx = max(mx, ps[i + H - 1][j + W - 1] - ps[i + H - 1][j - 1] - ps[i - 1][j + W - 1] + ps[i - 1][j - 1]);
        if (mx >= (H * W + 1) / 2) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    return ans;
}

/*int a[3001][3001];

int main()
{
    freopen("ss.inp", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int m, n, h, w;
    cin >> m >> n >> h >> w;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j) cin >> a[i][j];
    cout << rectangle(m, n, h, w, a);
    return 0;
}*/

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct
5 Correct 3 ms 1228 KB Output is correct
6 Correct 3 ms 1208 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct
5 Correct 3 ms 1228 KB Output is correct
6 Correct 3 ms 1208 KB Output is correct
7 Correct 18 ms 3916 KB Output is correct
8 Correct 18 ms 3932 KB Output is correct
9 Correct 17 ms 3812 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct
5 Correct 3 ms 1228 KB Output is correct
6 Correct 3 ms 1208 KB Output is correct
7 Correct 18 ms 3916 KB Output is correct
8 Correct 18 ms 3932 KB Output is correct
9 Correct 17 ms 3812 KB Output is correct
10 Correct 216 ms 22800 KB Output is correct
11 Correct 214 ms 22852 KB Output is correct
12 Correct 108 ms 15512 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct
5 Correct 3 ms 1228 KB Output is correct
6 Correct 3 ms 1208 KB Output is correct
7 Correct 18 ms 3916 KB Output is correct
8 Correct 18 ms 3932 KB Output is correct
9 Correct 17 ms 3812 KB Output is correct
10 Correct 216 ms 22800 KB Output is correct
11 Correct 214 ms 22852 KB Output is correct
12 Correct 108 ms 15512 KB Output is correct
13 Correct 2037 ms 140284 KB Output is correct
14 Correct 2085 ms 140228 KB Output is correct
15 Correct 1836 ms 133152 KB Output is correct