Submission #3002501


Source Code Expand

#include <iostream>
#include <algorithm>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

void chmax(int &a, int b) { a = max(a, b); }

int n, m;
int miku[101][101][101];

int main() {
	int i, j, k;
	
	cin >> n >> m;
	rep(i, n) {
		int a, b, c, w;
		cin >> a >> b >> c >> w;
		chmax(miku[a][b][c], w);
	}
	
	rep(i, 101) rep(j, 101) rep(k, 100) chmax(miku[i][j][k + 1], miku[i][j][k]);
	rep(j, 101) rep(k, 101) rep(i, 100) chmax(miku[i + 1][j][k], miku[i][j][k]);
	rep(k, 101) rep(i, 101) rep(j, 100) chmax(miku[i][j + 1][k], miku[i][j][k]);
	
	rep(i, m) {
		int x, y, z;
		cin >> x >> y >> z;
		cout << miku[x][y][z] << endl;
	}
	return 0;
}

//ループの順番を変更する。「学生が企業を選ぶ」ではなく「企業が学生を選ぶ」と考える。
//すると、(3面が開けた)長方形に値を書くのをN回したのち、各点について書かれた数のmaxを求める問題になる。
//これは、1次元のときと同様、1点に値を書き、最後に累積maxを3方向について行えばよい。
//計算量はN + M + 100^3程度になる。

Submission Info

Submission Time
Task C - Optimal Recommendations
User startcpp
Language C++14 (Clang 3.8.0)
Score 100
Code Size 1141 Byte
Status AC
Exec Time 365 ms
Memory 4736 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 24
Set Name Test Cases
All 10-random-00.txt, 10-random-01.txt, 10-random-02.txt, 10-random-03.txt, 10-random-04.txt, 20-absW-00.txt, 20-absW-01.txt, 20-absW-02.txt, 20-absW-03.txt, 20-absW-04.txt, 30-balance-00.txt, 30-balance-01.txt, 30-balance-02.txt, 30-balance-03.txt, 30-balance-04.txt, 40-limit_dim-00.txt, 40-limit_dim-01.txt, 40-limit_dim-02.txt, 40-limit_dim-03.txt, 40-limit_dim-04.txt, 40-limit_dim-05.txt, 40-limit_dim-06.txt, Corner1.txt, Sample1.txt
Case Name Status Exec Time Memory
10-random-00.txt AC 345 ms 4736 KB
10-random-01.txt AC 9 ms 4224 KB
10-random-02.txt AC 151 ms 4608 KB
10-random-03.txt AC 222 ms 4736 KB
10-random-04.txt AC 135 ms 4352 KB
20-absW-00.txt AC 318 ms 4480 KB
20-absW-01.txt AC 9 ms 4224 KB
20-absW-02.txt AC 178 ms 4352 KB
20-absW-03.txt AC 242 ms 4480 KB
20-absW-04.txt AC 95 ms 4352 KB
30-balance-00.txt AC 341 ms 4736 KB
30-balance-01.txt AC 9 ms 4224 KB
30-balance-02.txt AC 86 ms 4480 KB
30-balance-03.txt AC 209 ms 4480 KB
30-balance-04.txt AC 202 ms 4736 KB
40-limit_dim-00.txt AC 365 ms 4736 KB
40-limit_dim-01.txt AC 354 ms 4736 KB
40-limit_dim-02.txt AC 352 ms 4736 KB
40-limit_dim-03.txt AC 352 ms 4736 KB
40-limit_dim-04.txt AC 359 ms 4736 KB
40-limit_dim-05.txt AC 347 ms 4736 KB
40-limit_dim-06.txt AC 347 ms 4736 KB
Corner1.txt AC 9 ms 4224 KB
Sample1.txt AC 10 ms 4224 KB