oj.uz

Submission #250245

# Submission time Handle Problem Language Result Execution time Memory
250245 2020-07-17T10:05:17 Z Pbezz Building Bridges (CEOI17_building) C++14
30 / 100
 3000 ms 4476 KB 
#include <bits/stdc++.h>
using namespace std;

#define loop(i,n) for (ll i = 0; i < n; i++)

#define ll long long
#define INF 100000000005
#define MAXN 1000005
#define MOD 1000000000007
#define pb push_back 
#define mp make_pair
typedef pair<ll,ll> pii;


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	ll n,i,j,k;
	scanf("%lld",&n);

	ll h[n];
	ll w[n];
	ll dp[n];
	ll sum[n];

	for(i=0;i<n;i++){
	scanf("%lld",&h[i]);
	}
	for(i=0;i<n;i++){
	scanf("%lld",&w[i]);
	}

	sum[0]=w[0];
	for(i=1;i<n;i++){

	sum[i]=sum[i-1]+w[i];
	dp[i]=INF;

}

	dp[0]=0;

	for(i=1;i<n;i++){
		for(j=i-1;j>=0;j--){

		k=(h[i]-h[j])*(h[i]-h[j]);
		k+=dp[j];
		k+=(sum[i-1]-sum[j]);

		dp[i]=min(dp[i],k); 

		}
	}


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




return 0; 
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
building.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&h[i]);
  ~~~~~^~~~~~~~~~~~~~
building.cpp:32:7: 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 0 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 3053 ms 4476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 3053 ms 4476 KB Time limit exceeded
7 Halted 0 ms 0 KB -