oj.uz

Submission #521877

# Submission time Handle Problem Language Result Execution time Memory
521877 2022-02-03T10:54:41 Z antonioqbab Quality Of Living (IOI10_quality) C++14
100 / 100
 2176 ms 114116 KB 
#include <bits/stdc++.h>

using namespace std;

int rectangle(int N, int M, int y, int x, int q[3001][3001]){
    int left=1, right=N*M;
    while(left<right){
        int m=(left+right)/2;
        auto ok=[&](int cost){
            vector<vector<int>> s(N+1,vector<int>(M+1));
            for(int i = 1; i<=N;++i)
            for(int j=1;j<=M;++j)
                s[i][j]=((q[i-1][j-1]<cost)?-1:(q[i-1][j-1]==cost?0:1))+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
            for(int i=1;i<=N-y+1;++i)
            for(int j=1;j<=M-x+1;++j){
                int ii=i+y-1, jj=j+x-1;
                if(s[ii][jj]-s[i-1][jj]-s[ii][j-1]+s[i-1][j-1]<=0)
                    return 1;
            }
            return 0;
        };
        if(ok(m))
            right=m;
        else
            left=m+1;
    }
    return left;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 432 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 2 ms 820 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 16 ms 2744 KB Output is correct
8 Correct 17 ms 2716 KB Output is correct
9 Correct 15 ms 2596 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 432 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 2 ms 820 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 16 ms 2744 KB Output is correct
8 Correct 17 ms 2716 KB Output is correct
9 Correct 15 ms 2596 KB Output is correct
10 Correct 228 ms 19124 KB Output is correct
11 Correct 209 ms 18916 KB Output is correct
12 Correct 107 ms 11576 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 432 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 2 ms 820 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 16 ms 2744 KB Output is correct
8 Correct 17 ms 2716 KB Output is correct
9 Correct 15 ms 2596 KB Output is correct
10 Correct 228 ms 19124 KB Output is correct
11 Correct 209 ms 18916 KB Output is correct
12 Correct 107 ms 11576 KB Output is correct
13 Correct 2176 ms 114116 KB Output is correct
14 Correct 2165 ms 112964 KB Output is correct
15 Correct 1949 ms 104588 KB Output is correct