제출 #319168

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
319168		egod1537	매트 (KOI15_mat)	C++14	32 / 100	320 ms	71400 KiB

mat

#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

struct Line {
	int x, group;
	bool el;
};
struct Mat {
	int x1, y1, x2, y2, cost;
};

bool isCol(Mat& m1, Mat& m2) {
	if (m1.x2 <= m2.x1 || m2.x2 <= m1.x1) return false;
	if (m1.y2 <= m2.y1 || m2.y2 <= m1.y1) return false;
	return true;
}

int n, w;

int dp[3001][6001];
vector<Mat> mat;
vector<Line> line;
unordered_map<int, int> xidx;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> n >> w;

	for (int i = 0; i < n; i++) {
		int p, l, r, h, k; cin >> p >> l >> r >> h >> k;

		Mat now;

		now.x1 = l; now.x2 = r;
		if (p == 0)
			now.y1 = w - h, now.y2 = w;
		else
			now.y1 = 0, now.y2 = h;
		now.cost = k;

		mat.push_back(now);
	}

	sort(mat.begin(), mat.end(), [](const Mat & m1, const Mat & m2) -> bool {
		if (m1.x1 != m2.x1) return m1.x1 < m2.x1;
		return m1.x2 < m2.x2;
	});
	for (int i = 0; i < n; i++) {
		line.push_back({ mat[i].x1, i, false });
		line.push_back({ mat[i].x2, i, true });
	}
	sort(line.begin(), line.end(), [](const Line& l1, const Line& l2) -> bool {
		return l1.x < l2.x;
	});

	for (int i = 0; i < 2 * n; i++) xidx[line[i].x] = i;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 2*n; j++) {
			int& ret = dp[i][j];
			ret = mat[i].cost;

			if (j > 0)
				ret = max(ret, dp[i][j-1]);

			int to = line[j].group;

			if (line[j].x < mat[to].x2 || to >= i) continue;
			if (!line[j].el || isCol(mat[i], mat[to])) continue;

			//cout << i << " " << to << " " << line[j].x << "\n";

			//case1
			if (mat[to].x2 <= mat[i].x1)
				ret = max(ret, dp[to][xidx[mat[to].x2]] + mat[i].cost);
			//case2
			if (mat[to].x2 > mat[i].x1)
				ret = max(ret, dp[to][xidx[mat[i].x1]] + mat[i].cost);
		}
	}

	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 2 * n; j++) {
			//cout << dp[i][j] << " ";
			ans = max(ans, dp[i][j]);
		}
		//cout << "\n";
	}

	cout << ans;

	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 0 / 25
• Subtask 4: 11 / 11
• Subtask 5: 0 / 43