oj.uz

Submission #1023933

# Submission time Handle Problem Language Result Execution time Memory
1023933 2024-07-15T09:43:28 Z j_vdd16 Soccer Stadium (IOI23_soccer) C++17
52 / 100
 4500 ms 103100 KB 
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;


int biggest_stadium(int n, vvi f) {
	vvi up(n, vi(n)), down(n, vi(n)), left(n, vi(n)), right(n, vi(n));
	loop(x, n) {
		up[0][x] = 1 - f[0][x];
		for (int y = 1; y < n; y++) {
			if (f[y][x])
				up[y][x] = 0;
			else
				up[y][x] = up[y - 1][x] + 1;

		}

		down[n - 1][x] = 1 - f[n - 1][x];
		for (int y = n - 2; y >= 0; y--) {
			if (f[y][x])
				down[y][x] = 0;
			else
				down[y][x] = down[y + 1][x] + 1;
		}
	}
	loop(y, n) {
		left[y][0] = 1 - f[y][0];
		for (int x = 1; x < n; x++) {
			if (f[y][x])
				left[y][x] = 0;
			else
				left[y][x] = left[y][x - 1] + 1;

		}

		right[y][n - 1] = 1 - f[y][n - 1];
		for (int x = n - 2; x >= 0; x--) {
			if (f[y][x])
				right[y][x] = 0;
			else
				right[y][x] = right[y][x + 1] + 1;
		}

		//loop(y, n)
		//	cout << high[x][y] << low[x][y] << ' ';

		//cout << endl;
	}
	//cout << endl;

	int result = 0;
	loop(y, n) {
		loop(x, n) {
			if (f[y][x]) {
				cerr << "00 ";
				continue;
			}

			int count1 = 0;
			{
				int l = 0, r = n - 1;
				vii intervals;
				for (int y2 = y; y2 < y + down[y][x]; y2++) {
					l = max(l, x - left[y2][x] + 1);
					r = min(r, x + right[y2][x] - 1);

					intervals.push_back({ l, r });
					count1 += r - l + 1;
				}

				l = x - left[y][x] + 1;
				r = x + right[y][x] - 1;
				int idx = 0;
				for (int y2 = y - 1; y2 > y - up[y][x]; y2--) {
					l = max(l, x - left[y2][x] + 1);
					r = min(r, x + right[y2][x] - 1);

					while (idx < intervals.size()) {
						auto [li, ri] = intervals[idx];
						if (r < ri)
							l = max(l, li);

						if (l > li)
							r = min(r, ri);

						if (li >= l && ri <= r)
							break;

						idx++;
					}

					if (r < l)
						break;

					count1 += r - l + 1;
				}
			}
			int count2 = 0;
			{
				int l = 0, r = n - 1;
				vii intervals;
				for (int y2 = y; y2 > y - up[y][x]; y2--) {
					l = max(l, x - left[y2][x] + 1);
					r = min(r, x + right[y2][x] - 1);

					intervals.push_back({ l, r });
					count2 += r - l + 1;
				}

				l = x - left[y][x] + 1;
				r = x + right[y][x] - 1;

				int idx = 0;
				for (int y2 = y + 1; y2 < y + down[y][x]; y2++) {
					l = max(l, x - left[y2][x] + 1);
					r = min(r, x + right[y2][x] - 1);

					while (idx < intervals.size()) {
						auto [li, ri] = intervals[idx];
						if (r < ri)
							l = max(l, li);

						if (l > li)
							r = min(r, ri);

						if (li >= l && ri <= r)
							break;

						idx++;
					}

					if (r < l)
						break;

					count2 += r - l + 1;
				}
			}
			int count3 = 0;
			{
				int l = 0, r = n - 1;
				vii intervals;
				for (int x2 = x; x2 < x + right[y][x]; x2++) {
					l = max(l, y - up[y][x2] + 1);
					r = min(r, y + down[y][x2] - 1);

					intervals.push_back({ l, r });
					count3 += r - l + 1;
				}

				l = x - left[y][x] + 1;
				r = x + right[y][x] - 1;
				int idx = 0;
				for (int x2 = x - 1; x2 > x - left[y][x]; x2--) {
					l = max(l, y - up[y][x2] + 1);
					r = min(r, y + down[y][x2] - 1);

					while (idx < intervals.size()) {
						auto [li, ri] = intervals[idx];
						if (r < ri)
							l = max(l, li);

						if (l > li)
							r = min(r, ri);

						if (li >= l && ri <= r)
							break;

						idx++;
					}

					if (r < l)
						break;

					count3 += r - l + 1;
				}
			}
			int count4 = 0;
			{
				int l = 0, r = n - 1;
				vii intervals;
				for (int x2 = x; x2 > x - left[y][x]; x2--) {
					l = max(l, y - up[y][x2] + 1);
					r = min(r, y + down[y][x2] - 1);

					intervals.push_back({ l, r });
					count4 += r - l + 1;
				}

				l = x - left[y][x] + 1;
				r = x + right[y][x] - 1;
				int idx = 0;
				for (int x2 = x + 1; x2 < x + right[y][x]; x2++) {
					l = max(l, y - up[y][x2] + 1);
					r = min(r, y + down[y][x2] - 1);

					while (idx < intervals.size()) {
						auto [li, ri] = intervals[idx];
						if (r < ri)
							l = max(l, li);

						if (l > li)
							r = min(r, ri);

						if (li >= l && ri <= r)
							break;

						idx++;
					}

					if (r < l)
						break;

					count4 += r - l + 1;
				}
			}

			int count = max({ count1, count2, count3, count4} );
			result = max(result, count);
			cerr << count / 10 << count % 10 << ' ';
		}
		cerr << endl;
	}
	return result;
}

Compilation message

soccer.cpp: In function 'int biggest_stadium(int, vvi)':
soccer.cpp:104:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |      while (idx < intervals.size()) {
      |             ~~~~^~~~~~~~~~~~~~~~~~
soccer.cpp:144:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |      while (idx < intervals.size()) {
      |             ~~~~^~~~~~~~~~~~~~~~~~
soccer.cpp:183:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |      while (idx < intervals.size()) {
      |             ~~~~^~~~~~~~~~~~~~~~~~
soccer.cpp:222:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  222 |      while (idx < intervals.size()) {
      |             ~~~~^~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 1 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 82 ms 716 KB ok
8 Correct 3669 ms 7952 KB ok
9 Execution timed out 4521 ms 103100 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 0 ms 428 KB ok
10 Correct 1 ms 344 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 1 ms 348 KB ok
13 Correct 0 ms 348 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 1 ms 348 KB ok
10 Correct 0 ms 428 KB ok
11 Correct 1 ms 344 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 344 KB ok
16 Correct 1 ms 348 KB ok
17 Correct 1 ms 348 KB ok
18 Correct 1 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 1 ms 604 KB ok
26 Correct 1 ms 344 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 1 ms 348 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 1 ms 348 KB ok
12 Correct 0 ms 428 KB ok
13 Correct 1 ms 344 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 344 KB ok
18 Correct 1 ms 348 KB ok
19 Correct 1 ms 348 KB ok
20 Correct 1 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 1 ms 604 KB ok
28 Correct 1 ms 344 KB ok
29 Correct 1 ms 344 KB ok
30 Correct 7 ms 348 KB ok
31 Correct 3 ms 348 KB ok
32 Correct 3 ms 348 KB ok
33 Correct 2 ms 348 KB ok
34 Correct 3 ms 440 KB ok
35 Correct 2 ms 348 KB ok
36 Correct 2 ms 348 KB ok
37 Correct 3 ms 348 KB ok
38 Correct 2 ms 344 KB ok
39 Correct 2 ms 348 KB ok
40 Correct 5 ms 348 KB ok
41 Correct 5 ms 348 KB ok

Subtask #5
4.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 1 ms 348 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 1 ms 348 KB ok
12 Correct 0 ms 428 KB ok
13 Correct 1 ms 344 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 344 KB ok
18 Correct 1 ms 348 KB ok
19 Correct 1 ms 348 KB ok
20 Correct 1 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 1 ms 604 KB ok
28 Correct 1 ms 344 KB ok
29 Correct 1 ms 344 KB ok
30 Correct 7 ms 348 KB ok
31 Correct 3 ms 348 KB ok
32 Correct 3 ms 348 KB ok
33 Correct 2 ms 348 KB ok
34 Correct 3 ms 440 KB ok
35 Correct 2 ms 348 KB ok
36 Correct 2 ms 348 KB ok
37 Correct 3 ms 348 KB ok
38 Correct 2 ms 344 KB ok
39 Correct 2 ms 348 KB ok
40 Correct 5 ms 348 KB ok
41 Correct 5 ms 348 KB ok
42 Correct 982 ms 7504 KB ok
43 Correct 829 ms 7480 KB ok
44 Partially correct 1669 ms 7932 KB partial
45 Partially correct 2274 ms 8024 KB partial
46 Partially correct 1055 ms 7724 KB partial
47 Correct 3653 ms 8336 KB ok
48 Correct 1609 ms 8020 KB ok
49 Correct 1661 ms 7940 KB ok
50 Correct 2033 ms 7672 KB ok
51 Correct 1140 ms 8020 KB ok
52 Partially correct 470 ms 7504 KB partial
53 Partially correct 317 ms 7504 KB partial
54 Partially correct 461 ms 7696 KB partial
55 Partially correct 652 ms 7772 KB partial
56 Correct 1233 ms 7880 KB ok
57 Correct 2681 ms 8440 KB ok
58 Correct 2456 ms 8448 KB ok
59 Correct 2380 ms 8288 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 1 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 82 ms 716 KB ok
9 Correct 3669 ms 7952 KB ok
10 Execution timed out 4521 ms 103100 KB Time limit exceeded
11 Halted 0 ms 0 KB -