oj.uz

Submission #309498

# Submission time Handle Problem Language Result Execution time Memory
309498 2020-10-03T17:12:38 Z Kenzo_1114 Building Bridges (CEOI17_building) C++17
30 / 100
 3000 ms 3576 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
const long long int INF = 1e18 + 19;

int n;
long long int w[MAXN], h[MAXN], dp[MAXN];

int main ()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)	scanf("%lld", &h[i]);
	for(int i = 1; i <= n; i++)	
		scanf("%lld", &w[i]), w[i] += w[i - 1];
	
	for(int i = 2; i <= n; i++)
	{	
		dp[i] = INF;
		for(int j = 1; j < i; j++)
			dp[i] = min(dp[i], dp[j] + (h[j] - h[i]) * (h[j] - h[i]) + w[i - 1] - w[j]);
//		printf("dp[%d] = %lld\n", i, dp[i]);
	}

	printf("%lld\n", dp[n]);
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   11 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
building.cpp:12:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   12 |  for(int i = 1; i <= n; i++) scanf("%lld", &h[i]);
      |                              ~~~~~^~~~~~~~~~~~~~~
building.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   14 |   scanf("%lld", &w[i]), w[i] += w[i - 1];
      |   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3068 ms 3576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Execution timed out 3068 ms 3576 KB Time limit exceeded
7 Halted 0 ms 0 KB -