oj.uz

Submission #415262

# Submission time Handle Problem Language Result Execution time Memory
415262 2021-05-31T18:50:18 Z ak2006 Quality Of Living (IOI10_quality) C++14
100 / 100
 3329 ms 140312 KB 
#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

bool is(int n,int m,int mid,int g[3001][3001],int h,int w)
{
    vvi p(n + 1,vi(m + 1));
    for (int i = 1;i<=n;i++)for (int j = 1;j<=m;j++){
        p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
        if (g[i - 1][j - 1] > mid)p[i][j]++;
        else if (g[i - 1][j - 1] < mid)p[i][j]--;
    }
    for (int i = 1;i + h - 1 <=n;i++)
        for (int j = 1;j + w - 1 <= m;j++){
            if (p[i + h - 1][j + w - 1] - p[i + h - 1][j - 1] - p[i - 1][j + w - 1] + p[i - 1][j - 1] <= 0){
                return true;
            }
        }
    return false;
}

int rectangle(int n, int m, int h, int w, int Q[3001][3001]) {
	int l = 0,r = 1e9,ans = 1e9;
    while (l <= r){
        int mid = (l + r)/2;
        if (is(n,m,mid,Q,h,w)){ans = mid;r = mid - 1;}
        else l = mid + 1;
    }
    return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 424 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 424 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 716 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 4 ms 716 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 424 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 716 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 30 ms 2736 KB Output is correct
8 Correct 29 ms 2740 KB Output is correct
9 Correct 45 ms 2608 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 424 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 716 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 30 ms 2736 KB Output is correct
8 Correct 29 ms 2740 KB Output is correct
9 Correct 45 ms 2608 KB Output is correct
10 Correct 354 ms 19048 KB Output is correct
11 Correct 349 ms 18908 KB Output is correct
12 Correct 190 ms 11596 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 424 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 5 ms 716 KB Output is correct
5 Correct 4 ms 716 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 30 ms 2736 KB Output is correct
8 Correct 29 ms 2740 KB Output is correct
9 Correct 45 ms 2608 KB Output is correct
10 Correct 354 ms 19048 KB Output is correct
11 Correct 349 ms 18908 KB Output is correct
12 Correct 190 ms 11596 KB Output is correct
13 Correct 3329 ms 140312 KB Output is correct
14 Correct 3224 ms 140224 KB Output is correct
15 Correct 2969 ms 129560 KB Output is correct