oj.uz

Submission #61787

# Submission time Handle Problem Language Result Execution time Memory
61787 2018-07-26T17:14:36 Z IvanC Building Bridges (CEOI17_building) C++17
30 / 100
 3000 ms 4656 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;
const ll INF = 1e18;

ll dp[MAXN],H[MAXN],W[MAXN],pref[MAXN],b[MAXN],a[MAXN];
int N;

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]);
		pref[i] = W[i] + pref[i-1];
	}

	dp[1] = 0;
	a[1] = -2*H[1];
	b[1] = -pref[1] + dp[1] + H[1]*H[1];
	for(int i = 2;i<=N;i++){
		dp[i] = INF;
		ll fixed_val = H[i]*H[i] + pref[i-1];
		for(int j = 1;j<i;j++){
			dp[i] = min(dp[i], a[j]*H[i] + b[j] + fixed_val  );
		}
		a[i] = -2*H[i];
		b[i] = -pref[i] + dp[i] + H[i]*H[i];
	}

	cout << dp[N] << endl;

	return 0;
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
  ~~~~~^~~~~~~~~
building.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&H[i]);
   ~~~~~^~~~~~~~~~~~~~
building.cpp:19: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 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 3 ms 608 KB Output is correct
5 Correct 3 ms 608 KB Output is correct

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 3 ms 608 KB Output is correct
5 Correct 3 ms 608 KB Output is correct
6 Execution timed out 3048 ms 4656 KB Time limit exceeded
7 Halted 0 ms 0 KB -