# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
309975 | 2020-10-05T07:41:52 Z | sofapuden | Quality Of Living (IOI10_quality) | C++14 | 4364 ms | 140520 KB |
#include "quality.h" #include <bits/stdc++.h> using namespace std; int rectangle(int R, int C, int H, int W, int Q[3001][3001]) { int l = 0, r = R*C; int good; while(l < r){ int mid = (l+r+1)/2; vector<vector<int>> gri(R,vector<int>(C)); for(int i = 0; i < R; ++i){ for(int j = 0; j < C; ++j){ if(Q[i][j] < mid) gri[i][j] = -1; if(Q[i][j] > mid) gri[i][j] = 1; if(Q[i][j] == mid) gri[i][j] = 0; if(i)gri[i][j]+=gri[i-1][j]; if(j)gri[i][j]+=gri[i][j-1]; if(i && j)gri[i][j]-=gri[i-1][j-1]; } } int best = INT_MAX; for(int i = H-1; i < R; ++i){ for(int j = W-1; j < C; ++j){ int now = gri[i][j]; if(i >= H)now-=gri[i-H][j]; if(j >= W)now-=gri[i][j-W]; if(i >= H && j >= W)now+=gri[i-H][j-W]; best = min(best,now); } } if(best <= 0){r = mid-1;good = mid;} else l = mid; } return good; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 512 KB | Output is correct |
4 | Correct | 4 ms | 896 KB | Output is correct |
5 | Correct | 4 ms | 768 KB | Output is correct |
6 | Correct | 4 ms | 896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 512 KB | Output is correct |
4 | Correct | 4 ms | 896 KB | Output is correct |
5 | Correct | 4 ms | 768 KB | Output is correct |
6 | Correct | 4 ms | 896 KB | Output is correct |
7 | Correct | 36 ms | 2928 KB | Output is correct |
8 | Correct | 35 ms | 2820 KB | Output is correct |
9 | Correct | 30 ms | 2692 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 512 KB | Output is correct |
4 | Correct | 4 ms | 896 KB | Output is correct |
5 | Correct | 4 ms | 768 KB | Output is correct |
6 | Correct | 4 ms | 896 KB | Output is correct |
7 | Correct | 36 ms | 2928 KB | Output is correct |
8 | Correct | 35 ms | 2820 KB | Output is correct |
9 | Correct | 30 ms | 2692 KB | Output is correct |
10 | Correct | 449 ms | 19256 KB | Output is correct |
11 | Correct | 434 ms | 19004 KB | Output is correct |
12 | Correct | 220 ms | 11688 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 512 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 512 KB | Output is correct |
4 | Correct | 4 ms | 896 KB | Output is correct |
5 | Correct | 4 ms | 768 KB | Output is correct |
6 | Correct | 4 ms | 896 KB | Output is correct |
7 | Correct | 36 ms | 2928 KB | Output is correct |
8 | Correct | 35 ms | 2820 KB | Output is correct |
9 | Correct | 30 ms | 2692 KB | Output is correct |
10 | Correct | 449 ms | 19256 KB | Output is correct |
11 | Correct | 434 ms | 19004 KB | Output is correct |
12 | Correct | 220 ms | 11688 KB | Output is correct |
13 | Correct | 4354 ms | 140520 KB | Output is correct |
14 | Correct | 4364 ms | 140500 KB | Output is correct |
15 | Correct | 3939 ms | 129796 KB | Output is correct |