oj.uz

Submission #446913

# Submission time Handle Problem Language Result Execution time Memory
446913 2021-07-23T18:52:15 Z JerryLiu06 Quality Of Living (IOI10_quality) C++17
100 / 100
 2278 ms 167656 KB 
#include <bits/stdc++.h>

#include "quality.h"
 
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define mp make_pair
#define f first
#define s second
 
#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert 
#define ft front()
#define bk back()
#define pb push_back
#define pf push_front
 
#define lb lower_bound
#define ub upper_bound
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)
#define EACH(a, x) for (auto& a : x)
 
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); }
ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
template<class T> void remDup(vector<T>& v) { sor(v); v.erase(unique(all(v)), v.end()); }
 
const int MOD = 1e9 + 7;
const int MX = 3001;
const ll INF = 1e18;

int R, C, H, W, Q[MX][MX]; int pref[MX][MX];

bool valid(int median) {
    memset(pref, 0, sizeof pref); FOR(i, 1, R + 1) FOR(j, 1, C + 1) {
        pref[i][j] = (Q[i - 1][j - 1] > median ? 1 : -1); pref[i][j] += pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
    }
    FOR(i, 1, R + 1) FOR(j, 1, R + 1) {
        if (i + H - 1 > R || j + W - 1 > C) continue; 

        if (pref[i + H - 1][j + W - 1] - pref[i - 1][j + W - 1] - pref[i + H - 1][j - 1] + pref[i - 1][j - 1] < 0) return true; 
    }
    return false;
}

int rectangle(int _R, int _C, int _H, int _W, int _Q[MX][MX]) {
    R = _R; C = _C; H = _H; W = _W; F0R(i, MX) F0R(j, MX) Q[i][j] = _Q[i][j];
    
    int low = 1; int high = R * C; int res = -1;

    while (low <= high) { int mid = (low + high) / 2;
        if (valid(mid)) { high = mid - 1; res = mid; } else low = mid + 1;
    }
    return res;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 70944 KB Output is correct
2 Correct 76 ms 70964 KB Output is correct
3 Correct 75 ms 70960 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 70944 KB Output is correct
2 Correct 76 ms 70964 KB Output is correct
3 Correct 75 ms 70960 KB Output is correct
4 Correct 93 ms 71320 KB Output is correct
5 Correct 88 ms 71324 KB Output is correct
6 Correct 94 ms 71328 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 70944 KB Output is correct
2 Correct 76 ms 70964 KB Output is correct
3 Correct 75 ms 70960 KB Output is correct
4 Correct 93 ms 71320 KB Output is correct
5 Correct 88 ms 71324 KB Output is correct
6 Correct 94 ms 71328 KB Output is correct
7 Correct 122 ms 72900 KB Output is correct
8 Correct 125 ms 72908 KB Output is correct
9 Correct 116 ms 72824 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 70944 KB Output is correct
2 Correct 76 ms 70964 KB Output is correct
3 Correct 75 ms 70960 KB Output is correct
4 Correct 93 ms 71320 KB Output is correct
5 Correct 88 ms 71324 KB Output is correct
6 Correct 94 ms 71328 KB Output is correct
7 Correct 122 ms 72900 KB Output is correct
8 Correct 125 ms 72908 KB Output is correct
9 Correct 116 ms 72824 KB Output is correct
10 Correct 333 ms 85560 KB Output is correct
11 Correct 326 ms 85444 KB Output is correct
12 Correct 227 ms 80088 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 70944 KB Output is correct
2 Correct 76 ms 70964 KB Output is correct
3 Correct 75 ms 70960 KB Output is correct
4 Correct 93 ms 71320 KB Output is correct
5 Correct 88 ms 71324 KB Output is correct
6 Correct 94 ms 71328 KB Output is correct
7 Correct 122 ms 72900 KB Output is correct
8 Correct 125 ms 72908 KB Output is correct
9 Correct 116 ms 72824 KB Output is correct
10 Correct 333 ms 85560 KB Output is correct
11 Correct 326 ms 85444 KB Output is correct
12 Correct 227 ms 80088 KB Output is correct
13 Correct 2260 ms 157500 KB Output is correct
14 Correct 2278 ms 157420 KB Output is correct
15 Correct 2103 ms 167656 KB Output is correct