oj.uz

Submission #319591

# Submission time Handle Problem Language Result Execution time Memory
319591 2020-11-05T15:53:09 Z parsabahrami Building Bridges (CEOI17_building) C++17
30 / 100
 3000 ms 3556 KB 
//! The Leader Of Retards Bemola
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<ll, ll> pll;
 
#define sz(x)                       (ll) x.size()
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second

ll Pow(ll a, ll b, ll md, ll ans = 1) {
    for (; b; b >>= 1, a = a * a % md)
        if (b & 1)
            ans = ans * a % md;
    return ans % md;
}
const ll MAXN = 1e5 + 10;
const ll INF  = 1e18;
const ll MOD  = 1e9 + 7;
ll dp[MAXN], H[MAXN], W[MAXN], ps[MAXN], n;

int main() {
	scanf("%lld", &n);
	for (ll i = 1; i <= n; i++) {
		scanf("%lld", &H[i]);
	}
	for (ll i = 1; i <= n; i++) {
		scanf("%lld", &W[i]);
	}
	fill(dp, dp + MAXN, INF);
	partial_sum(W, W + MAXN, ps);
	dp[1] = 0;
	for (ll i = 2; i <= n; i++) {
		for (ll j = 1; j < i; j++) {
			dp[i] = min(dp[i], dp[j] - ps[j] + H[j] * H[j] - 2 * H[i] * H[j]);
		}
		dp[i] += ps[i - 1] + H[i] * H[i];
	}
	printf("%lld\n", dp[n]);
    return 0;
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |  scanf("%lld", &n);
      |  ~~~~~^~~~~~~~~~~~
building.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |   scanf("%lld", &H[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
building.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |   scanf("%lld", &W[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
0 / 30.0

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