oj.uz

답안 #1066529

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1066529 2024-08-20T00:30:59 Z HD1 Rectangles (IOI19_rect) C++14
15 / 100
 566 ms 83224 KB 
#include "rect.h"
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
#define sz(s) int (s.size())
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAX=1e6;
ll n,m;
ll mxf[82][82][82], mxc[82][82][82];
vector< vector<int> > A;
void loco(vector<int> s, int x){//filas
	for(int i=1; i<m-1; i++){
		int mx=s[i];
		for(int j=i; j<m-1; j++){
			mx=max(mx,s[j]);
			mxf[x][i][j]=mx;
		}
	}
	return;
}
void loca(vector<int> s, int x){//columnas
	for(int i=1; i<n-1; i++){
		int mx=s[i];
		for(int j=i; j<n-1; j++){
			mx=max(mx,s[j]);
			mxc[x][i][j]=mx;
		}
	}
	return;
}
bool validf(int mx, int i, int l, int r){
	return A[i][l-1]>mx && A[i][r+1]>mx;
}
bool validc(int mx, int j, int l, int r){
	return A[l-1][j]>mx && A[r+1][j]>mx;
}
bool rectangle(int a, int b, int x, int y){
	bool good=true;
	for(int i=a; i<=x; i++){//por filas
		good&=validf(mxf[i][b][y], i, b, y);
	}
	for(int j=b; j<=y; j++){//por columnas
		good&=validc(mxc[j][a][x], j, a, x);
	}
	return good;
}
int fijo(int i1, int j1){
	int ans=0;
	for(int i=i1; i<n-1; i++){
		for(int j=j1; j<m-1; j++){
			if(rectangle(i1, j1, i, j)) ans++;
		}
	}
	return ans;
}
long long count_rectangles(vector< vector<int> > a) {
	A=a;
	n=sz(a);
	m=sz(a[0]);
	for(int i=0; i<n; i++){
		loco(a[i], i);
	}
	vector<int> c;
	for(int j=0; j<m; j++){
		for(int i=0; i<n; i++){
			c.pb(a[i][j]);
		}
		loca(c,j);
		c.clear();
	}
	int ans=0;
	for(int i=1; i<n-1; i++){
		for(int j=1; j<m-1; j++){
			ans+=fijo(i,j);
		}
	}
	return ans;
}
/*
6 5
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
*/

Subtask #1
8.0 / 8.0

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

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 4 ms 1628 KB Output is correct
3 Correct 4 ms 1628 KB Output is correct
4 Correct 4 ms 1628 KB Output is correct
5 Correct 3 ms 1628 KB Output is correct
6 Correct 7 ms 1628 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 6 ms 1740 KB Output is correct
10 Correct 6 ms 1628 KB Output is correct
11 Correct 7 ms 1628 KB Output is correct
12 Correct 6 ms 1628 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 604 KB Output is correct
16 Correct 0 ms 440 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 5 ms 1748 KB Output is correct
20 Correct 1 ms 1116 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 566 ms 8796 KB Output is correct
23 Correct 557 ms 8968 KB Output is correct
24 Correct 555 ms 8800 KB Output is correct
25 Correct 477 ms 8796 KB Output is correct
26 Correct 484 ms 8888 KB Output is correct
27 Correct 489 ms 8904 KB Output is correct
28 Correct 497 ms 8940 KB Output is correct
29 Correct 103 ms 4700 KB Output is correct

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 4 ms 1628 KB Output is correct
3 Correct 4 ms 1628 KB Output is correct
4 Correct 4 ms 1628 KB Output is correct
5 Correct 3 ms 1628 KB Output is correct
6 Correct 7 ms 1628 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 6 ms 1740 KB Output is correct
10 Correct 6 ms 1628 KB Output is correct
11 Correct 7 ms 1628 KB Output is correct
12 Correct 6 ms 1628 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 604 KB Output is correct
16 Correct 0 ms 440 KB Output is correct
17 Correct 566 ms 8796 KB Output is correct
18 Correct 557 ms 8968 KB Output is correct
19 Correct 555 ms 8800 KB Output is correct
20 Correct 477 ms 8796 KB Output is correct
21 Correct 484 ms 8888 KB Output is correct
22 Correct 489 ms 8904 KB Output is correct
23 Correct 497 ms 8940 KB Output is correct
24 Correct 103 ms 4700 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 5 ms 1748 KB Output is correct
28 Correct 1 ms 1116 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Runtime error 7 ms 10332 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 4 ms 1628 KB Output is correct
3 Correct 4 ms 1628 KB Output is correct
4 Correct 4 ms 1628 KB Output is correct
5 Correct 3 ms 1628 KB Output is correct
6 Correct 7 ms 1628 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 6 ms 1740 KB Output is correct
10 Correct 6 ms 1628 KB Output is correct
11 Correct 7 ms 1628 KB Output is correct
12 Correct 6 ms 1628 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 604 KB Output is correct
16 Correct 0 ms 440 KB Output is correct
17 Correct 566 ms 8796 KB Output is correct
18 Correct 557 ms 8968 KB Output is correct
19 Correct 555 ms 8800 KB Output is correct
20 Correct 477 ms 8796 KB Output is correct
21 Correct 484 ms 8888 KB Output is correct
22 Correct 489 ms 8904 KB Output is correct
23 Correct 497 ms 8940 KB Output is correct
24 Correct 103 ms 4700 KB Output is correct
25 Runtime error 7 ms 10332 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 11 ms 5208 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 5 ms 1748 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Runtime error 175 ms 83224 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 4 ms 1628 KB Output is correct
3 Correct 4 ms 1628 KB Output is correct
4 Correct 4 ms 1628 KB Output is correct
5 Correct 3 ms 1628 KB Output is correct
6 Correct 7 ms 1628 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 6 ms 1740 KB Output is correct
10 Correct 6 ms 1628 KB Output is correct
11 Correct 7 ms 1628 KB Output is correct
12 Correct 6 ms 1628 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 604 KB Output is correct
16 Correct 0 ms 440 KB Output is correct
17 Correct 566 ms 8796 KB Output is correct
18 Correct 557 ms 8968 KB Output is correct
19 Correct 555 ms 8800 KB Output is correct
20 Correct 477 ms 8796 KB Output is correct
21 Correct 484 ms 8888 KB Output is correct
22 Correct 489 ms 8904 KB Output is correct
23 Correct 497 ms 8940 KB Output is correct
24 Correct 103 ms 4700 KB Output is correct
25 Runtime error 7 ms 10332 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -