답안 #340443

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
340443	2020-12-27T15:46:42 Z	Marlov	Rectangles (IOI19_rect)	C++14	37 / 100	5000 ms	1048580 KB

rect

/*
Code by @marlov       
*/
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <utility>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <iterator>
#include <bitset>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

long long count_rectangles(vector< vector<int> > a){
	int N=a.size();
	int M=a[0].size();
	int result=0;

	bool rows[N][M][M];
	bool cols[M][N][N];
	for(int i=1;i<N-1;i++){
		for(int j=1;j<M-1;j++){
			int cm=0;
			for(int k=j;k<M-1;k++){
				cm=max(cm,a[i][k]);
				if(cm<a[i][j-1]&&cm<a[i][k+1]) rows[i][j][k]=true;
				else rows[i][j][k]=false;
			}
		}
	}

	for(int i=1;i<M-1;i++){
		for(int j=1;j<N-1;j++){
			int cm=0;
			for(int k=j;k<N-1;k++){
				cm=max(cm,a[k][i]);
				if(cm<a[j-1][i]&&cm<a[k+1][i]){
					cols[i][j][k]=true;
					//cout<<"cols:"<<i<<" "<<j<<" "<<k<<" "<<a[k][i]<<endl;
				}else{
					cols[i][j][k]=false;
				}
			}
		}
	}

	for(int i=1;i<N-1;i++){
		for(int j=1;j<M-1;j++){
			for(int k=j;k<M-1;k++){
				for(int x=i;x<N-1;x++){
					if(!rows[x][j][k]) break;
					bool pos=true;
					for(int y=j;y<=k;y++){
						if(!cols[y][i][x]) pos=false;
					}
					//if (pos) cout<<i<<" "<<x<<" "<<j<<" "<<k<<endl;
					if(pos) result++;
				}
			}
		}
	}
	
return result;

}
/*
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cout<<count_rectangles( {{4, 8, 7, 5, 6},{7, 4, 10, 3, 5},{9, 7, 20, 14, 2},{9, 14, 7, 3, 6},{5, 7, 5, 2, 7},{4, 5, 13, 5, 6}} );
    return 0;
}
*/


/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1,n=0?)
	* do smth instead of nothing and stay organized
*/

Subtask #1

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	0 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	1 ms	364 KB	Output is correct
20	Correct	1 ms	364 KB	Output is correct
21	Correct	1 ms	364 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	0 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	15 ms	1388 KB	Output is correct
18	Correct	18 ms	1388 KB	Output is correct
19	Correct	15 ms	1388 KB	Output is correct
20	Correct	3 ms	1388 KB	Output is correct
21	Correct	3 ms	1388 KB	Output is correct
22	Correct	3 ms	1388 KB	Output is correct
23	Correct	3 ms	1388 KB	Output is correct
24	Correct	1 ms	748 KB	Output is correct
25	Correct	1 ms	364 KB	Output is correct
26	Correct	1 ms	364 KB	Output is correct
27	Correct	1 ms	364 KB	Output is correct
28	Correct	1 ms	364 KB	Output is correct
29	Correct	1 ms	364 KB	Output is correct

Subtask #3

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	0 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	15 ms	1388 KB	Output is correct
18	Correct	18 ms	1388 KB	Output is correct
19	Correct	15 ms	1388 KB	Output is correct
20	Correct	3 ms	1388 KB	Output is correct
21	Correct	3 ms	1388 KB	Output is correct
22	Correct	3 ms	1388 KB	Output is correct
23	Correct	3 ms	1388 KB	Output is correct
24	Correct	1 ms	748 KB	Output is correct
25	Correct	674 ms	16396 KB	Output is correct
26	Correct	669 ms	16512 KB	Output is correct
27	Correct	692 ms	16500 KB	Output is correct
28	Correct	29 ms	16248 KB	Output is correct
29	Correct	33 ms	16236 KB	Output is correct
30	Correct	32 ms	16492 KB	Output is correct
31	Correct	43 ms	16492 KB	Output is correct
32	Correct	35 ms	16108 KB	Output is correct
33	Correct	1 ms	364 KB	Output is correct
34	Correct	1 ms	364 KB	Output is correct
35	Correct	1 ms	364 KB	Output is correct
36	Correct	1 ms	364 KB	Output is correct
37	Correct	1 ms	364 KB	Output is correct

Subtask #4

0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	0 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	15 ms	1388 KB	Output is correct
18	Correct	18 ms	1388 KB	Output is correct
19	Correct	15 ms	1388 KB	Output is correct
20	Correct	3 ms	1388 KB	Output is correct
21	Correct	3 ms	1388 KB	Output is correct
22	Correct	3 ms	1388 KB	Output is correct
23	Correct	3 ms	1388 KB	Output is correct
24	Correct	1 ms	748 KB	Output is correct
25	Correct	674 ms	16396 KB	Output is correct
26	Correct	669 ms	16512 KB	Output is correct
27	Correct	692 ms	16500 KB	Output is correct
28	Correct	29 ms	16248 KB	Output is correct
29	Correct	33 ms	16236 KB	Output is correct
30	Correct	32 ms	16492 KB	Output is correct
31	Correct	43 ms	16492 KB	Output is correct
32	Correct	35 ms	16108 KB	Output is correct
33	Correct	1323 ms	676844 KB	Output is correct
34	Correct	1295 ms	676900 KB	Output is correct
35	Correct	1301 ms	676904 KB	Output is correct
36	Correct	1296 ms	676716 KB	Output is correct
37	Execution timed out	5075 ms	676748 KB	Time limit exceeded
38	Halted	0 ms	0 KB	-

Subtask #5

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	6636 KB	Output is correct
2	Correct	12 ms	4844 KB	Output is correct
3	Correct	13 ms	6508 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	13 ms	6636 KB	Output is correct
6	Correct	17 ms	6636 KB	Output is correct
7	Correct	13 ms	6636 KB	Output is correct
8	Correct	13 ms	6508 KB	Output is correct
9	Correct	14 ms	6636 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct

Subtask #6

0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Runtime error	1322 ms	1048580 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
3	Halted	0 ms	0 KB	-

Subtask #7

0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	0 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	15 ms	1388 KB	Output is correct
18	Correct	18 ms	1388 KB	Output is correct
19	Correct	15 ms	1388 KB	Output is correct
20	Correct	3 ms	1388 KB	Output is correct
21	Correct	3 ms	1388 KB	Output is correct
22	Correct	3 ms	1388 KB	Output is correct
23	Correct	3 ms	1388 KB	Output is correct
24	Correct	1 ms	748 KB	Output is correct
25	Correct	674 ms	16396 KB	Output is correct
26	Correct	669 ms	16512 KB	Output is correct
27	Correct	692 ms	16500 KB	Output is correct
28	Correct	29 ms	16248 KB	Output is correct
29	Correct	33 ms	16236 KB	Output is correct
30	Correct	32 ms	16492 KB	Output is correct
31	Correct	43 ms	16492 KB	Output is correct
32	Correct	35 ms	16108 KB	Output is correct
33	Correct	1323 ms	676844 KB	Output is correct
34	Correct	1295 ms	676900 KB	Output is correct
35	Correct	1301 ms	676904 KB	Output is correct
36	Correct	1296 ms	676716 KB	Output is correct
37	Execution timed out	5075 ms	676748 KB	Time limit exceeded
38	Halted	0 ms	0 KB	-