oj.uz

Submission #104260

# Submission time Handle Problem Language Result Execution time Memory
104260 2019-04-04T13:56:41 Z luciocf Building Bridges (CEOI17_building) C++14
0 / 100
 53 ms 2952 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Runtime error 3 ms 556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1892 KB Output is correct
2 Correct 53 ms 2952 KB Output is correct
3 Incorrect 40 ms 2808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Runtime error 3 ms 556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -