Submission #83309

#	Time	Username	Problem	Language	Result	Execution time	Memory
83309		fredbr	Cover (COCI18_cover)	C++17	120 / 120	5 ms	852 KiB

cover

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

// o resultado pode ultrapassar o inteiro normal
typedef long long ll;
typedef pair<ll, ll> ii;

const int maxn = 5010;

ii v[maxn];
ii d[maxn];

ll dp[maxn];

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

	int n;
	cin >> n;

	for (int i = 1; i <= n; i++) {

		cin >> v[i].ff >> v[i].ss;

		// tratamos somente com o primeiro quadrante
		v[i].ff = abs(v[i].ff);
		v[i].ss = abs(v[i].ss);
	}

	sort(v+1, v+n+1);

	// ponteiro para o ultimo elemento processado
	int cur = 0;

	for (int i = 1; i <= n; i++) {

		// remove o elemento anterior caso irrelevante
		while (cur > 0 and v[i].ss >= d[cur].ss) cur--;

		// coloca o elemento atual
		d[++cur] = v[i];
	}

	// lembrar de recontar o numero de elementos
	n = cur;

	// torna dp[i] infinito para todo i != 0
	memset(dp, 0x3f, maxn*8);
	dp[0] = 0ll;

	// loop que calcula a dp para todos os i
	for (int i = 1; i <= n; i++) {

		// loop para calcular o dp[i]
		for (int j = 0; j < i; j++) {

			dp[i] = min(dp[i], dp[j] + d[j+1].ss*d[i].ff);
		}
	}

	cout << dp[n]*4ll << "\n";

	return 0;
}

• Subtask 1: 120 / 120