# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
591672 | 2022-07-07T18:13:34 Z | ogibogi2004 | Quality Of Living (IOI10_quality) | C++14 | 5000 ms | 58164 KB |
#include "quality.h" #include<bits/stdc++.h> using namespace std; const int MAXN=3001; int table[MAXN][MAXN]; int t1[MAXN][MAXN]; int h,w,r,c; bool check(int val) { for(int i=0;i<MAXN;i++) { for(int j=0;j<MAXN;j++) { if(table[i][j]<=val)t1[i][j]=1; else t1[i][j]=0; } } int cnt=0; for(int i=0;i<h;i++) { for(int j=0;j<w;j++) { if(t1[i][j])cnt++; } } if(cnt>h*w/2)return 1; int x=0,y=0; queue<char>q; for(int i=0;i<c-w;i++)q.push('R'); q.push('D'); for(int i=0;i<c-w;i++)q.push('L'); q.push('D'); while(x!=r-h||y!=c-w) { char dir=q.front(); q.push(q.front()); q.pop(); if(dir=='R') { for(int i=x;i<x+h;i++) { if(t1[i][y]==1)cnt--; if(t1[i][y+w]==1)cnt++; } y++; } else if(dir=='L') { for(int i=x;i<x+h;i++) { if(t1[i][y+w-1]==1)cnt--; if(t1[i][y-1]==1)cnt++; } y--; } else if(dir=='D') { for(int j=y;j<y+w;j++) { if(t1[x][j]==1)cnt--; if(t1[x+h][j]==1)cnt++; } x++; } if(cnt>h*w/2)return 1; } return 0; } int rectangle(int R, int C, int H, int W, int Q[3001][3001]) { r=R;c=C;h=H;w=W; for(int i=0;i<R;i++) { for(int j=0;j<C;j++) { table[i][j]=Q[i][j]; } } int low=1,high=R*C,mid,best; while(low<=high) { mid=(low+high)/2; if(check(mid)) { best=mid; high=mid-1; } else low=mid+1; } return best; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 87 ms | 35848 KB | Output is correct |
2 | Correct | 91 ms | 35856 KB | Output is correct |
3 | Correct | 85 ms | 35796 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 87 ms | 35848 KB | Output is correct |
2 | Correct | 91 ms | 35856 KB | Output is correct |
3 | Correct | 85 ms | 35796 KB | Output is correct |
4 | Correct | 120 ms | 36528 KB | Output is correct |
5 | Correct | 150 ms | 36520 KB | Output is correct |
6 | Correct | 130 ms | 36528 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 87 ms | 35848 KB | Output is correct |
2 | Correct | 91 ms | 35856 KB | Output is correct |
3 | Correct | 85 ms | 35796 KB | Output is correct |
4 | Correct | 120 ms | 36528 KB | Output is correct |
5 | Correct | 150 ms | 36520 KB | Output is correct |
6 | Correct | 130 ms | 36528 KB | Output is correct |
7 | Correct | 301 ms | 39236 KB | Output is correct |
8 | Correct | 167 ms | 39116 KB | Output is correct |
9 | Correct | 267 ms | 39116 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 87 ms | 35848 KB | Output is correct |
2 | Correct | 91 ms | 35856 KB | Output is correct |
3 | Correct | 85 ms | 35796 KB | Output is correct |
4 | Correct | 120 ms | 36528 KB | Output is correct |
5 | Correct | 150 ms | 36520 KB | Output is correct |
6 | Correct | 130 ms | 36528 KB | Output is correct |
7 | Correct | 301 ms | 39236 KB | Output is correct |
8 | Correct | 167 ms | 39116 KB | Output is correct |
9 | Correct | 267 ms | 39116 KB | Output is correct |
10 | Execution timed out | 5030 ms | 58164 KB | Time limit exceeded |
11 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 87 ms | 35848 KB | Output is correct |
2 | Correct | 91 ms | 35856 KB | Output is correct |
3 | Correct | 85 ms | 35796 KB | Output is correct |
4 | Correct | 120 ms | 36528 KB | Output is correct |
5 | Correct | 150 ms | 36520 KB | Output is correct |
6 | Correct | 130 ms | 36528 KB | Output is correct |
7 | Correct | 301 ms | 39236 KB | Output is correct |
8 | Correct | 167 ms | 39116 KB | Output is correct |
9 | Correct | 267 ms | 39116 KB | Output is correct |
10 | Execution timed out | 5030 ms | 58164 KB | Time limit exceeded |
11 | Halted | 0 ms | 0 KB | - |