Submission #104253

#	Time	Username	Problem	Language	Result	Execution time	Memory
104253		luciocf	Building Bridges (CEOI17_building)	C++14	30 / 100	43 ms	8576 KiB

building

#include <bits/stdc++.h>

using namespace std;

const int maxn_ = 1e3+10;
const int maxn = 1e5+10;
const int add = 20;
const long long inf = 2e18+10;

typedef long long ll;

int n;

int ind[42];

ll menor[42];

ll h[maxn], w[maxn];

ll dp[maxn_][maxn_];

ll cost(int i, int j)
{
	return (h[j]-h[i])*(h[j]-h[i]);
}

ll solve(int pos, int ant)
{
	if (pos == n) return cost(n, ant);
	if (dp[pos][ant] != -1) return dp[pos][ant];

	if (pos == 1) return dp[pos][ant] = solve(pos+1, 1);

	ll caso1 = 1ll*w[pos]+solve(pos+1, ant);
	ll caso2 = cost(pos, ant)+solve(pos+1, pos);

	return dp[pos][ant] = min(caso1, caso2);
}

int main(void)
{
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
		scanf("%lld", &h[i]);

	ll S = 0ll;
	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &w[i]);
		if (i != 1 && i != n) S += w[i];
	}

	if (n <= 1000)
	{
		memset(dp, -1, sizeof dp);
		printf("%lld\n", solve(1, 0));
		return 0;
	}

	for (int i = 0; i <= 40; i++)
		menor[i] = inf, ind[i] = -1;

	ll ans = cost(1, n);
	menor[w[2]+add] = h[2], ind[w[2]+add] = 2;

	for (int i = 3; i < n; i++)
	{
		for (int j = 0; j <= 40; j++)
		{
			if (ind[j] == -1) continue;
			ans = min(ans, cost(1, ind[j])+cost(ind[j], i)+cost(i, n)+S-w[i]-w[ind[j]]);
		}

		if (h[i] < menor[w[i]+add])
			menor[w[i]+add] = h[i], ind[w[i]+add] = i;

		if (h[i] == menor[w[i]+add] && w[i] > w[ind[w[i]+add]])
			menor[w[i]+add] = h[i], ind[w[i]+add] = i;
	}

	for (int i = 2; i < n; i++)
		ans = min(ans, cost(1, i)+cost(i, n)+S-w[i]);

	printf("%lld\n", ans);
}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
building.cpp:45:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &h[i]);
   ~~~~~^~~~~~~~~~~~~~~
building.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &w[i]);
   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40