# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
406758 |
2021-05-18T04:29:54 Z |
ngrace |
Rectangles (IOI19_rect) |
C++14 |
|
1809 ms |
190068 KB |
#include "rect.h"
#include <vector>
#include <iostream>
#include <set>
using namespace std;
#define v vector
#define pii pair<int,int>
#define fi first
#define se second
long long count_rectangles(std::vector<std::vector<int> > a) {
long long out=0;
int R=a.size();
int C=a[0].size();
bool subSix=true;
for(int i=0;i<R;i++){//check for sub six
for(int j=0;j<C;j++){
if(a[i][j]>1){
subSix=false;
break;
}
}
if(!subSix){
break;
}
}
if(subSix){
//find sub rectangles with dp[i][j] = {min(dp[i-1][j-1].first, dp[i][j-1].first),
// min(dp[i-1][j-1].second, dp[i-1][j].second)}
//then for each rectangle check the border.
//can speed up by making so only consider if dp[i-1][j-1].first and dp[i][j-1].first are equal
v<v<pii>> dp(R,v<pii>(C,{-1,-1}));
for(int r=1;r<R-1;r++){
for(int c=1;c<C-1;c++){
if(a[r][c]==0){
int f=r;
int s=c;
int r1=dp[r-1][c-1].fi;
int r2=dp[r-1][c].fi;
int c1=dp[r-1][c-1].se;
int c2=dp[r][c-1].se;
if(c1==c2 && c1!=-1){
s=max(c1,1);
}
if(r1==r2 && r1!=-1){
f=max(r1,1);
}
if(c1==-1 && c2!=-1){
s=c2;
}
else if(r1==-1 && r2!=-1){
f=r2;
}
dp[r][c]={f,s};
}
}
}
//check dp table
/**for(int r=0;r<R;r++){
for(int c=0;c<C;c++){
cout<<"("<<dp[r][c].fi<<" "<<dp[r][c].se<<") ";
}
cout<<endl;
}**/
//dp table is now made
//iterate from bottom right to top left
//for every distinct dp[i][j] value check borders of that rect then mark as covered
set<pii> checked;
checked.insert({-1,-1});
for(int r=R-1;r>0;r--){
for(int c=C-1;c>0;c--){
if(a[r][c]==0 && checked.find(dp[r][c])==checked.end()){
checked.insert(dp[r][c]);
int r1=dp[r][c].fi;
int c1=dp[r][c].se;
bool works=true;
for(int i=r1;i<=r;i++){
if(a[i][c1-1]==0 || a[i][c+1]==0){
works=false;
break;
}
}
for(int j=c1;j<=c;j++){
if(a[r1-1][j]==0 || a[r+1][j]==0){
works=false;
break;
}
}
if(works){
out++;
}
}
}
}
}
else if((R<=200 && C<=200) || R<=3){//sub one, two, three and five
for(int r1=1;r1<R-1;r1++){
for(int c1=1;c1<C-1;c1++){
for(int r2=r1;r2<R-1;r2++){
for(int c2=c1;c2<C-1;c2++){
//have rect with top left r1, c1, bottom right r2, c2
//check every value of the rect
bool works=true;
for(int r=r1;r<=r2;r++){
for(int c=c1;c<=c2;c++){
if(a[r1-1][c]<=a[r][c]){
works=false;
break;
}
if(a[r2+1][c]<=a[r][c]){
works=false;
break;
}
if(a[r][c1-1]<=a[r][c]){
works=false;
break;
}
if(a[r][c2+1]<=a[r][c]){
works=false;
break;
}
}
if(!works){
break;
}
}
if(works){
out++;
}
}
}
}
}
}
else{
//full
}
return out;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
204 KB |
Output is correct |
3 |
Correct |
2 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
2 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
2 ms |
204 KB |
Output is correct |
10 |
Correct |
2 ms |
204 KB |
Output is correct |
11 |
Correct |
2 ms |
204 KB |
Output is correct |
12 |
Correct |
2 ms |
288 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
204 KB |
Output is correct |
3 |
Correct |
2 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
2 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
2 ms |
204 KB |
Output is correct |
10 |
Correct |
2 ms |
204 KB |
Output is correct |
11 |
Correct |
2 ms |
204 KB |
Output is correct |
12 |
Correct |
2 ms |
288 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
1 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
1 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
47 ms |
344 KB |
Output is correct |
23 |
Correct |
48 ms |
384 KB |
Output is correct |
24 |
Correct |
46 ms |
352 KB |
Output is correct |
25 |
Correct |
36 ms |
332 KB |
Output is correct |
26 |
Correct |
39 ms |
332 KB |
Output is correct |
27 |
Correct |
39 ms |
332 KB |
Output is correct |
28 |
Correct |
41 ms |
332 KB |
Output is correct |
29 |
Correct |
11 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
204 KB |
Output is correct |
3 |
Correct |
2 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
2 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
2 ms |
204 KB |
Output is correct |
10 |
Correct |
2 ms |
204 KB |
Output is correct |
11 |
Correct |
2 ms |
204 KB |
Output is correct |
12 |
Correct |
2 ms |
288 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
47 ms |
344 KB |
Output is correct |
18 |
Correct |
48 ms |
384 KB |
Output is correct |
19 |
Correct |
46 ms |
352 KB |
Output is correct |
20 |
Correct |
36 ms |
332 KB |
Output is correct |
21 |
Correct |
39 ms |
332 KB |
Output is correct |
22 |
Correct |
39 ms |
332 KB |
Output is correct |
23 |
Correct |
41 ms |
332 KB |
Output is correct |
24 |
Correct |
11 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
204 KB |
Output is correct |
28 |
Correct |
1 ms |
204 KB |
Output is correct |
29 |
Correct |
1 ms |
204 KB |
Output is correct |
30 |
Correct |
1809 ms |
820 KB |
Output is correct |
31 |
Correct |
1752 ms |
816 KB |
Output is correct |
32 |
Correct |
1789 ms |
964 KB |
Output is correct |
33 |
Correct |
1388 ms |
676 KB |
Output is correct |
34 |
Correct |
1545 ms |
740 KB |
Output is correct |
35 |
Correct |
1551 ms |
892 KB |
Output is correct |
36 |
Correct |
1507 ms |
872 KB |
Output is correct |
37 |
Correct |
1456 ms |
844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
204 KB |
Output is correct |
3 |
Correct |
2 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
2 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
2 ms |
204 KB |
Output is correct |
10 |
Correct |
2 ms |
204 KB |
Output is correct |
11 |
Correct |
2 ms |
204 KB |
Output is correct |
12 |
Correct |
2 ms |
288 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
47 ms |
344 KB |
Output is correct |
18 |
Correct |
48 ms |
384 KB |
Output is correct |
19 |
Correct |
46 ms |
352 KB |
Output is correct |
20 |
Correct |
36 ms |
332 KB |
Output is correct |
21 |
Correct |
39 ms |
332 KB |
Output is correct |
22 |
Correct |
39 ms |
332 KB |
Output is correct |
23 |
Correct |
41 ms |
332 KB |
Output is correct |
24 |
Correct |
11 ms |
332 KB |
Output is correct |
25 |
Correct |
1809 ms |
820 KB |
Output is correct |
26 |
Correct |
1752 ms |
816 KB |
Output is correct |
27 |
Correct |
1789 ms |
964 KB |
Output is correct |
28 |
Correct |
1388 ms |
676 KB |
Output is correct |
29 |
Correct |
1545 ms |
740 KB |
Output is correct |
30 |
Correct |
1551 ms |
892 KB |
Output is correct |
31 |
Correct |
1507 ms |
872 KB |
Output is correct |
32 |
Correct |
1456 ms |
844 KB |
Output is correct |
33 |
Correct |
1 ms |
204 KB |
Output is correct |
34 |
Correct |
1 ms |
204 KB |
Output is correct |
35 |
Correct |
1 ms |
204 KB |
Output is correct |
36 |
Correct |
1 ms |
204 KB |
Output is correct |
37 |
Correct |
1 ms |
204 KB |
Output is correct |
38 |
Incorrect |
18 ms |
7184 KB |
Output isn't correct |
39 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
332 KB |
Output is correct |
2 |
Correct |
11 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
15 ms |
412 KB |
Output is correct |
6 |
Correct |
17 ms |
404 KB |
Output is correct |
7 |
Correct |
16 ms |
408 KB |
Output is correct |
8 |
Correct |
13 ms |
392 KB |
Output is correct |
9 |
Correct |
15 ms |
296 KB |
Output is correct |
10 |
Correct |
1 ms |
304 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
477 ms |
87064 KB |
Output is correct |
8 |
Correct |
1016 ms |
189064 KB |
Output is correct |
9 |
Correct |
999 ms |
190044 KB |
Output is correct |
10 |
Correct |
987 ms |
190068 KB |
Output is correct |
11 |
Correct |
94 ms |
54628 KB |
Output is correct |
12 |
Correct |
170 ms |
103680 KB |
Output is correct |
13 |
Correct |
209 ms |
110632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
2 ms |
204 KB |
Output is correct |
3 |
Correct |
2 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
2 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
2 ms |
204 KB |
Output is correct |
10 |
Correct |
2 ms |
204 KB |
Output is correct |
11 |
Correct |
2 ms |
204 KB |
Output is correct |
12 |
Correct |
2 ms |
288 KB |
Output is correct |
13 |
Correct |
1 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
1 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
47 ms |
344 KB |
Output is correct |
18 |
Correct |
48 ms |
384 KB |
Output is correct |
19 |
Correct |
46 ms |
352 KB |
Output is correct |
20 |
Correct |
36 ms |
332 KB |
Output is correct |
21 |
Correct |
39 ms |
332 KB |
Output is correct |
22 |
Correct |
39 ms |
332 KB |
Output is correct |
23 |
Correct |
41 ms |
332 KB |
Output is correct |
24 |
Correct |
11 ms |
332 KB |
Output is correct |
25 |
Correct |
1809 ms |
820 KB |
Output is correct |
26 |
Correct |
1752 ms |
816 KB |
Output is correct |
27 |
Correct |
1789 ms |
964 KB |
Output is correct |
28 |
Correct |
1388 ms |
676 KB |
Output is correct |
29 |
Correct |
1545 ms |
740 KB |
Output is correct |
30 |
Correct |
1551 ms |
892 KB |
Output is correct |
31 |
Correct |
1507 ms |
872 KB |
Output is correct |
32 |
Correct |
1456 ms |
844 KB |
Output is correct |
33 |
Incorrect |
18 ms |
7184 KB |
Output isn't correct |
34 |
Halted |
0 ms |
0 KB |
- |