Submission #544505

#	Time	Username	Problem	Language	Result	Execution time	Memory
544505		model_code	Team Contest (JOI22_team)	C++17	27 / 100	322 ms	120916 KiB

team

/*
	[ SAMPLE SOURCE CODE FOR "TEAM CONTEST" SUBTASK 5 ]
	Algorithm: Please refer to the editorial.
	Time Complexity: O(MAX^3)
*/

#include <vector>
#include <cassert>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	// step #1. read input
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> X(N), Y(N), Z(N);
	for (int i = 0; i < N; i++) {
		cin >> X[i] >> Y[i] >> Z[i];
	}
	
	// step #2. record in 3D array
	int SX = *max_element(X.begin(), X.end()) + 1;
	int SY = *max_element(Y.begin(), Y.end()) + 1;
	int SZ = *max_element(Z.begin(), Z.end()) + 1;
	assert(SX <= 301 && SY <= 301 && SZ <= 301);
	vector<vector<vector<bool> > > exists(SX, vector<vector<bool> >(SY, vector<bool>(SZ, false)));
	for (int i = 0; i < N; i++) {
		exists[X[i]][Y[i]][Z[i]] = true;
	}
	
	// step #3. calculate 3D cumulative sum
	vector<vector<vector<int> > > sum(SX + 1, vector<vector<int> >(SY + 1, vector<int>(SZ + 1)));
	for (int i = 0; i < SX; i++) {
		for (int j = 0; j < SY; j++) {
			for (int k = 0; k < SZ; k++) {
				sum[i + 1][j + 1][k + 1] = (exists[i][j][k] ? 1 : 0);
			}
		}
	}
	for (int i = 0; i < SX; i++) {
		for (int j = 0; j < SY; j++) {
			for (int k = 0; k < SZ; k++) {
				sum[i + 1][j + 1][k + 1] += sum[i][j + 1][k + 1];
			}
		}
	}
	for (int i = 0; i < SX; i++) {
		for (int j = 0; j < SY; j++) {
			for (int k = 0; k < SZ; k++) {
				sum[i + 1][j + 1][k + 1] += sum[i + 1][j][k + 1];
			}
		}
	}
	for (int i = 0; i < SX; i++) {
		for (int j = 0; j < SY; j++) {
			for (int k = 0; k < SZ; k++) {
				sum[i + 1][j + 1][k + 1] += sum[i + 1][j + 1][k];
			}
		}
	}
	
	// step #4. brute force
	int answer = -1;
	for (int x = 1; x < SX; x++) {
		for (int y = 1; y < SY; y++) {
			for (int z = 1; z < SZ; z++) {
				int sumx = sum[x + 1][y][z] - sum[x][y][z];
				int sumy = sum[x][y + 1][z] - sum[x][y][z];
				int sumz = sum[x][y][z + 1] - sum[x][y][z];
				if (sumx >= 1 && sumy >= 1 && sumz >= 1) {
					answer = x + y + z;
				}
			}
		}
	}
	
	// step #5. output the answer
	cout << answer << endl;
	
	return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 27