oj.uz

Submission #319121

# Submission time Handle Problem Language Result Execution time Memory
319121 2020-11-04T01:16:12 Z egod1537 매트 (KOI15_mat) C++14
21 / 100
 1000 ms 110372 KB 
#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

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;
}

//i, j번째 매트가 겹치는지
bool col[3001][3001];
//i번재 매트가 x_j 이하에 있는지
bool least[3001][6001];

int n, w;
vector<int> sx;
unordered_map<int, int> xidx;
int dp[3001][6001];
int cache[3001][6001];

vector<Mat> arr;

int main() {
	memset(cache, -1, sizeof(cache));

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

	cin >> n >> w;
	arr.resize(n);

	for (int i = 0; i < n; i++) {
		int p, x1, x2, y, cost; 
		cin >> p >> x1 >> x2 >> y >> cost;

		if (p == 0) {
			arr[i].x1 = x1; arr[i].x2 = x2;
			arr[i].y1 = w-y; arr[i].y2 = w;
		}
		else {
			arr[i].x1 = x1; arr[i].x2 = x2;
			arr[i].y1 = 0; arr[i].y2 = y;
		}

		arr[i].cost = cost;
		sx.push_back(x1); sx.push_back(x2);
	}

	sort(sx.begin(), sx.end());
	sx.erase(unique(sx.begin(), sx.end()), sx.end());

	int idx = 0;
	for (int w : sx) xidx[w] = idx++;

	sort(arr.begin(), arr.end(), [](Mat m1, 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++) {
		int sidx = xidx[arr[i].x2];
		for (int j = sidx; j < xidx.size(); j++)
			least[i][j] = true;
		for (int j = 0; j < n; j++)
			col[i][j] = isCol(arr[i], arr[j]);
	}

	int ans = 0;
	for (int line = 0; line < xidx.size(); line++) {
		for (int i = 0; i < n; i++) {
			int ni = min(line, xidx[arr[i].x1]);
			int v = 0;

			for (int j = 0; j < i; j++) {
				if (col[i][j] || !least[j][line]) continue;

				int nj = min(line, xidx[arr[j].x2]);

				if (v <= dp[j][min(ni, nj)])
					cache[i][line] = j;

				v = max(v, dp[j][min(ni, nj)]);
			}

			dp[i][line] = v + arr[i].cost;
			if (line > 0)
				dp[i][line] = max(dp[i][line], dp[i][line-1]);

			ans = max(ans, dp[i][line]);
		}
	}

	cout << ans << "\n";
	return 0;
}

Compilation message

mat.cpp: In function 'int main()':
mat.cpp:69:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::unordered_map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   for (int j = sidx; j < xidx.size(); j++)
      |                      ~~^~~~~~~~~~~~~
mat.cpp:76:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::unordered_map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for (int line = 0; line < xidx.size(); line++) {
      |                     ~~~~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 71028 KB Output is correct
2 Correct 39 ms 70892 KB Output is correct
3 Correct 39 ms 70892 KB Output is correct
4 Correct 40 ms 70884 KB Output is correct
5 Correct 39 ms 70884 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 70884 KB Output is correct
2 Correct 40 ms 70880 KB Output is correct
3 Correct 39 ms 70924 KB Output is correct
4 Correct 39 ms 70884 KB Output is correct
5 Correct 40 ms 70884 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1097 ms 108968 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 110372 KB Time limit exceeded
2 Halted 0 ms 0 KB -