oj.uz

Submission #1108555

# Submission time Handle Problem Language Result Execution time Memory
1108555 2024-11-04T12:27:44 Z wayzzjr Building Bridges (CEOI17_building) C++17
0 / 100
 43 ms 67144 KB 
// ----------------------- TEMPLATE NO.4 ---------------------------
#include<bits/stdc++.h>
using namespace std;

#define ll long long
const ll mod = 1e9 + 7;
const int N = 1e5 + 100;
const int MX = 1e6 + 5;

// loops
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define ROF(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)

// others :>
#define nl '\n'
//----------------------------------SOLUTION-----------------------------------//

int n;
ll w[N], h[N], dp[N], pre[N];

struct line{
	ll a, b;
	line() : a(0), b(0) {}
	line(ll a, ll b) : a(a), b(b) {}

	ll calc(ll x){
		return a * x + b;
	}

	ll slope() { return a; }
} f[4 * MX];

#define mid ((lx + rx) / 2)
void update(int idx, int lx, int rx, line x){
	if(lx == rx){
		f[idx] = (x.calc(lx) < f[idx].calc(lx) ? x : f[idx]);
		return; 
	}

	if(f[idx].calc(mid) > x.calc(mid)) swap(x, f[idx]);

	if(f[idx].slope() < x.slope())
		update(idx<<1, lx, mid, x);
	if(f[idx].slope() > x.slope())
		update(idx<<1|1, mid+1, rx, x);
}

ll query(int idx, int lx, int rx, int p){
	ll cur = f[idx].calc(p);

	if(lx == rx) return cur;

	if(p <= mid)
		return min(cur, query(idx<<1, lx, mid, p));
	else
		return min(cur, query(idx<<1|1, mid+1, rx, p));
}

ll sqr(ll x){
	return x * x;
}

void solve(){
	cin >> n;
	FOR(i, 1, n) cin >> h[i];
	FOR(i, 1, n) cin >> w[i];
	FOR(i, 1, n) pre[i] = pre[i-1] + w[i];

	update(1, 0, MX, line(-2 * h[1], sqr(h[1]) - pre[1]) );
	FOR(i, 2, n){
		dp[i] = query(1, 0, MX, h[i]) + sqr(h[i]) + pre[i-1];
		update(1, 0, MX, line(-2 * h[i], dp[i] + sqr(h[i]) - pre[i]));
	}
	cout << dp[n];
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	#define Wayzz "name"
	if (fopen (Wayzz".inp", "r")) {
		freopen (Wayzz".inp", "r", stdin);
		freopen (Wayzz".out", "w", stdout);
	}
	int T = 1;
    while(T--) solve();
	cerr <<"\nTime Elapse: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

Compilation message

building.cpp: In function 'int main()':
building.cpp:81:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |   freopen (Wayzz".inp", "r", stdin);
      |   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:82:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   freopen (Wayzz".out", "w", stdout);
      |   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 64248 KB Output is correct
2 Correct 13 ms 64144 KB Output is correct
3 Correct 9 ms 64220 KB Output is correct
4 Correct 9 ms 64080 KB Output is correct
5 Incorrect 9 ms 64164 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 66120 KB Output is correct
2 Correct 43 ms 67144 KB Output is correct
3 Correct 41 ms 67144 KB Output is correct
4 Correct 38 ms 66896 KB Output is correct
5 Incorrect 36 ms 66896 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 64248 KB Output is correct
2 Correct 13 ms 64144 KB Output is correct
3 Correct 9 ms 64220 KB Output is correct
4 Correct 9 ms 64080 KB Output is correct
5 Incorrect 9 ms 64164 KB Output isn't correct
6 Halted 0 ms 0 KB -