Submission #104260

#	Time	Username	Problem	Language	Result	Execution time	Memory
104260		luciocf	Building Bridges (CEOI17_building)	C++14	0 / 100	53 ms	2952 KiB

building

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5+10;
const long long inf = 2e18+10;

typedef long long ll;

int n;
int ind[60];

ll menor[60];
ll h[maxn], w[maxn];

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

int main(void)
{
	int add = 20;
	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];
	}

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

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

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

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

Compilation message (stderr)

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

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