oj.uz

Submission #1045389

# Submission time Handle Problem Language Result Execution time Memory
1045389 2024-08-05T22:44:31 Z HD1 Rectangles (IOI19_rect) C++14
8 / 100
 53 ms 75016 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[32][32][32], mxc[32][32][32];
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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 7 ms 860 KB Output is correct
3 Correct 7 ms 936 KB Output is correct
4 Correct 6 ms 860 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 7 ms 940 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 7 ms 936 KB Output is correct
10 Correct 7 ms 856 KB Output is correct
11 Correct 8 ms 860 KB Output is correct
12 Correct 7 ms 940 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 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 6 ms 860 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 7 ms 860 KB Output is correct
3 Correct 7 ms 936 KB Output is correct
4 Correct 6 ms 860 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 7 ms 940 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 7 ms 936 KB Output is correct
10 Correct 7 ms 856 KB Output is correct
11 Correct 8 ms 860 KB Output is correct
12 Correct 7 ms 940 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 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 6 ms 860 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Runtime error 1 ms 1116 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 7 ms 860 KB Output is correct
3 Correct 7 ms 936 KB Output is correct
4 Correct 6 ms 860 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 7 ms 940 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 7 ms 936 KB Output is correct
10 Correct 7 ms 856 KB Output is correct
11 Correct 8 ms 860 KB Output is correct
12 Correct 7 ms 940 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 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Runtime error 1 ms 1116 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 7 ms 860 KB Output is correct
3 Correct 7 ms 936 KB Output is correct
4 Correct 6 ms 860 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 7 ms 940 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 7 ms 936 KB Output is correct
10 Correct 7 ms 856 KB Output is correct
11 Correct 8 ms 860 KB Output is correct
12 Correct 7 ms 940 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 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Runtime error 1 ms 1116 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 1116 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 6 ms 860 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Runtime error 53 ms 75016 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 7 ms 860 KB Output is correct
3 Correct 7 ms 936 KB Output is correct
4 Correct 6 ms 860 KB Output is correct
5 Correct 5 ms 860 KB Output is correct
6 Correct 7 ms 940 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 7 ms 936 KB Output is correct
10 Correct 7 ms 856 KB Output is correct
11 Correct 8 ms 860 KB Output is correct
12 Correct 7 ms 940 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 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Runtime error 1 ms 1116 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -