oj.uz

Submission #309942

# Submission time Handle Problem Language Result Execution time Memory
309942 2020-10-05T03:56:18 Z ttnhuy313 Cover (COCI18_cover) C++14
120 / 120
 23 ms 768 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 5005, oo = 1e18;
int n, f[N], g[N], x[N], y[N], lst[N];
map <int, int> mpList;

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> n;
	for (int i = 1; i <= n; ++i) {
		int x, y;
		cin >> x >> y;
		x = abs(x), y = abs(y);
		mpList[x] = max(mpList[x], y);
	}
	int m = 0;
	for (auto V : mpList) {
		int _x = V.first, _y = V.second;
		m++;
		x[m] = _x;
		y[m] = _y;
	}
	for (int i = m; i >= 1; --i) {
		int j = i + 1;
		for (j = i + 1; j <= m; ++j) {
			if (y[j] > y[i]) break;
		}
		lst[i] = j - 1;
	}
	for (int i = 1; i <= m; ++i) {
		f[i] = g[i] = oo;
	}
	f[1] = g[1] = x[1] * y[1];
	for (int i = 2; i <= m; ++i) {
		int k = i;
		for (k = i; k >= 1; --k) if (y[k] > y[i])
			break;
		k++;
		f[i] = x[i] * y[i] + g[k - 1];
		g[i] = f[i];
		for (int j = 1; j < i; ++j) if (lst[j] >= i)
			g[i] = min(g[i], f[j] + (x[i] - x[j]) * y[j]);
	}
	g[m] <<= 2;
	cout << g[m] << endl;

	return 0;
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 10 ms 640 KB Output is correct
10 Correct 23 ms 768 KB Output is correct