oj.uz

Submission #310388

# Submission time Handle Problem Language Result Execution time Memory
310388 2020-10-06T19:59:32 Z pedroslrey Building Bridges (CEOI17_building) C++14
30 / 100
 3000 ms 3704 KB 
#include <bits/stdc++.h>

using namespace std;
using lli = long long int;

const int MAXN = 1e5 + 10;
const lli INF = 1e18 + 19;

lli xs[MAXN];
lli wpref[MAXN];
lli dp[MAXN];
 
int main() {
	int n;
	scanf("%d", &n);

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

	for (int i = 1; i <= n; ++i) {	
		scanf("%lld", &wpref[i]); 
		wpref[i] += wpref[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] + wpref[i - 1] - wpref[j] + 
				(xs[j] - xs[i])*(xs[j] - xs[i]));
	}
 
	printf("%lld\n", dp[n]);
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
building.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |   scanf("%lld", &xs[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~
building.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   21 |   scanf("%lld", &wpref[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 2 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 3044 ms 3704 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 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Execution timed out 3044 ms 3704 KB Time limit exceeded
7 Halted 0 ms 0 KB -