oj.uz

Submission #319176

# Submission time Handle Problem Language Result Execution time Memory
319176 2020-11-04T11:32:55 Z egod1537 매트 (KOI15_mat) C++14
32 / 100
 288 ms 71428 KB 
#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.x2 != m2.x2) return m1.x2 < m2.x2;
		return m1.x1 < m2.x1;
	});
	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 {
		if(l1.x != l2.x) return l1.x < l2.x;
		return l1.el > l2.el;
	});

	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 (mat[i].x2 < line[j].x) 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][j] + 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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 71272 KB Output is correct
2 Correct 171 ms 71428 KB Output is correct
3 Correct 162 ms 71268 KB Output is correct
4 Correct 162 ms 71396 KB Output is correct
5 Correct 157 ms 71268 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 71268 KB Output is correct
2 Incorrect 288 ms 71416 KB Output isn't correct
3 Halted 0 ms 0 KB -