oj.uz

Submission #245588

# Submission time Handle Problem Language Result Execution time Memory
245588 2020-07-06T21:21:01 Z tatyam Quality Of Living (IOI10_quality) C++17
100 / 100
 2421 ms 90720 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define name3(a,b,c,d,...) d
#define rep1(b) for(int i = 0; i < b; i++)
#define rep2(i,b) for(int i = 0; i < b; i++)
#define rep3(i,a,b) for(int i = a; i < b; i++)
#define rep(...) name3(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
 
#include "quality.h"

int rectangle(int R, int C, int H, int W, int Q[3001][3001]){
    auto check = [&](int x) -> bool {
        vector s(R + 1, vector<int>(C + 1));
        rep(R) rep(j, C) s[i + 1][j + 1] = Q[i][j] <= x;
        rep(R + 1) rep(j, C) s[i][j + 1] += s[i][j];
        rep(R) rep(j, C + 1) s[i + 1][j] += s[i][j];
        rep(i, H, R + 1) rep(j, W, C + 1) if(s[i][j] - s[i - H][j] - s[i][j - W] + s[i - H][j - W] >= (H * W + 1) / 2) return true;
        return false;
    };
    int ok = R * C, ng = 0;
    while(ok - ng > 1){
        int cen = (ok + ng) / 2;
        (check(cen) ? ok : ng) = cen;
    }
    return ok;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 6 ms 896 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 24 ms 2840 KB Output is correct
8 Correct 25 ms 2836 KB Output is correct
9 Correct 23 ms 2772 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 24 ms 2840 KB Output is correct
8 Correct 25 ms 2836 KB Output is correct
9 Correct 23 ms 2772 KB Output is correct
10 Correct 244 ms 19056 KB Output is correct
11 Correct 241 ms 18992 KB Output is correct
12 Correct 119 ms 11672 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 7 ms 896 KB Output is correct
5 Correct 7 ms 896 KB Output is correct
6 Correct 6 ms 896 KB Output is correct
7 Correct 24 ms 2840 KB Output is correct
8 Correct 25 ms 2836 KB Output is correct
9 Correct 23 ms 2772 KB Output is correct
10 Correct 244 ms 19056 KB Output is correct
11 Correct 241 ms 18992 KB Output is correct
12 Correct 119 ms 11672 KB Output is correct
13 Correct 2404 ms 90668 KB Output is correct
14 Correct 2421 ms 90720 KB Output is correct
15 Correct 2131 ms 85188 KB Output is correct