oj.uz

답안 #1023926

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1023926 2024-07-15T09:38:34 Z j_vdd16 축구 경기장 (IOI23_soccer) C++17
0 / 100
 4500 ms 102964 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, x - left[y][x2] + 1);
					r = min(r, x + right[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, x - left[y][x2] + 1);
					r = min(r, x + right[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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB ok

Subtask #1
0.0 / 6.0

# 결과 실행 시간 메모리 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 0 ms 348 KB ok
6 Partially correct 0 ms 348 KB partial
7 Partially correct 69 ms 728 KB partial
8 Correct 3584 ms 8020 KB ok
9 Execution timed out 4568 ms 102964 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Incorrect 0 ms 348 KB wrong
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Incorrect 0 ms 348 KB wrong
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 Incorrect 0 ms 348 KB wrong
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 Incorrect 0 ms 348 KB wrong
7 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 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 Partially correct 0 ms 348 KB partial
8 Partially correct 69 ms 728 KB partial
9 Correct 3584 ms 8020 KB ok
10 Execution timed out 4568 ms 102964 KB Time limit exceeded
11 Halted 0 ms 0 KB -