oj.uz

Submission #104253

# Submission time Handle Problem Language Result Execution time Memory
104253 2019-04-04T13:26:53 Z luciocf Building Bridges (CEOI17_building) C++14
30 / 100
 43 ms 8576 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8320 KB Output is correct
2 Correct 10 ms 8320 KB Output is correct
3 Correct 10 ms 8320 KB Output is correct
4 Correct 24 ms 8576 KB Output is correct
5 Correct 28 ms 8440 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 2920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8320 KB Output is correct
2 Correct 10 ms 8320 KB Output is correct
3 Correct 10 ms 8320 KB Output is correct
4 Correct 24 ms 8576 KB Output is correct
5 Correct 28 ms 8440 KB Output is correct
6 Incorrect 43 ms 2920 KB Output isn't correct
7 Halted 0 ms 0 KB -