Submission #1256871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256871		baodat	Building Bridges (CEOI17_building)	C++20	100 / 100	57 ms	65352 KiB

building

/*
This bozo is cheating, plz ban him cfs!!!!!
bozo: top1severtin
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long int
#define eb emplace_back
#define ins insert
#define pb push_back
#define popcount(x) __builtin_popcountll(x)
#define clz(x) __builtin_clz(x)
#define ctz(x) __builtin_ctz(x)
#define MASK(x) (1ll << x)
#define all(x) (x).begin(), (x).end()
#define	all_rev(x) (x).rbegin(), (x).rend()
#define FOR(i, l, r) for(int i = (l), _ = (int)(r); i <= _; i++)
#define FORD(i, l, r) for(int i = (l), _ = (int)(r); i >= _; i--)
#define SFOR(i, l, r, x) for(int i = (l), _ = (int)(r); i <= _; i += (x))
#define SFORD(i, l, r, x) for(int i = (l), _ = (int)(r); i >= _; i -= (x))
#define db double
#define ldb long double
#define ms(x, val) memset(x, val, sizeof(x))
#define sp(x) setprecision(x) << fixed
#define ff first
#define ss second
#define rsz resize
#define el "\n"
#define div ______div
template<typename T> void debug_1d(const T& a, const string& name) {
	if(a.empty()) {
		cerr << name << " is empty!\n";
		return;
	}
	FOR(i, 0, a.size() - 1) {
		cerr << name << "[" << i << "]: " << a[i] << el;
	}
}
template<typename T> void debug_2d(const T& a, const string& name) {
	if(a.empty()) {
		cerr << name << "is empty!\n";
		return;
	}
	FOR(i, 0, a.size() - 1) {
		if(a[i].empty()) {
			cerr << name << "[" << i << "] is empty!\n";
			continue;
		}
		FOR(j, 0, a[i].size() - 1) {
			cerr << name << "[" << i << "]" << "[" << j << "]: " << a[i][j] << " ";
		}
		cerr << el;
	}
}
template<typename T> void debug_var(const T& a, const string& name) {
	cerr << name << ": " << a << el;
}
template<typename T> void debug_map(const T& a, const string& name) {
	if(a.empty()) {
		cerr << name << " is empty!\n";
		return;
	}
	for(const auto& it : a) {
		cerr << name << "[" << it.ff << "]: " << it.ss << el;
	}
}
template<typename T> void debug_stack(stack<T> s, const string& name) {
	if (s.empty()) {
		cerr << name << " is empty!\n";
		return;
	}
	int idx = 0;
	while (!s.empty()) {
		cerr << name << "[" << idx++ << "]: " << s.top() << '\n';
		s.pop();
	}
}

template<typename T> void debug_queue(queue<T> q, const string& name) {
	if (q.empty()) {
		cerr << name << " is empty!\n";
		return;
	}
	int idx = 0;
	while (!q.empty()) {
		cerr << name << "[" << idx++ << "]: " << q.front() << '\n';
		q.pop();
	}
}
template<typename T> void debug_pq(priority_queue<T> pq, const string& name) {
	if (pq.empty()) {
		cerr << name << " is empty!\n";
		return;
	}
	int idx = 0;
	while (!pq.empty()) {
		cerr << name << "[" << idx++ << "]: " << pq.top() << '\n';
		pq.pop();
	}
}
void read_file() {
#define NAME "txt"
	freopen(NAME ".INP", "r", stdin);
	freopen(NAME ".OUT", "w", stdout);
}
typedef __int128 i128;
typedef pair<int, int> pii;
typedef pair<char, int> pci;
typedef pair<int, char> pic;
typedef pair<string, int> psi;
typedef pair<int, string> pis;
typedef vector<vector<int>> vector2d_int;
typedef vector<vector<char>> vector2d_char;
const long long oo = 2e18;
const int oo_int = 2e9;
const int mod = 1e9 + 7;
const int mod998 = 998244353;
bool more_test = 0;
void prepare(){
}
int line_equation(pii line, int x){
    return line.ff * x + line.ss;
}
struct lichao_tree{
    int n;
    vector<pii>tree;
    lichao_tree(int __n){
        n = __n;
        tree.assign(4 * n + 5, {0, oo});
    }
    void update(int i, int l, int r, pii line){
        int m = (l + r) >> 1;
        int cur_eq = line_equation(line, m);
        int cur_tree_eq = line_equation(tree[i], m);
        if(cur_eq < cur_tree_eq) swap(tree[i], line);
        if(l == r) return;
        int cl = (i << 1) , cr = (cl | 1);
        if(line_equation(line, l) < line_equation(tree[i], l)){
            update(cl, l, m, line);
        }
        else if(line_equation(line, r) < line_equation(tree[i], r)){
            update(cr, m + 1, r, line);
        }
    }
    void update(pii line){
        update(1, 0, n, line);
    }
    int query(int i, int l, int r, int x){
        int m = (l + r) >> 1;
        int res = line_equation(tree[i], x);
        if(l == r) return res;
        int cl = (i << 1), cr = (cl | 1);
        if(x <= m) return min(res, query(cl, l, m, x));
        else return min(res, query(cr, m + 1, r, x));
    }
    int query(int x){
        return query(1, 0, n, x);
    }
};
void solve() {
    int n, sum = 0;
    cin >> n;
    vector<int> h(n + 1), w(n + 1);
    FOR(i, 1, n) cin >> h[i];
    FOR(i, 1, n) cin >> w[i], sum += w[i];
    vector<int> dp(n + 1, oo);
    dp[1] = -w[1];
    lichao_tree tree(1e6);
    ///base case:
    tree.update({-2 * h[1], h[1] * h[1] + dp[1]});
    FOR(i, 2, n){
        int cand = tree.query(h[i]);
        dp[i] = cand + h[i] * h[i] - w[i];
        tree.update({-2 * h[i], h[i] * h[i] + dp[i]});
    }
    cout << sum + dp[n];
}
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	//read_file();
	prepare();
	int t = 1;
	if(more_test) cin >> t;
	while(t--)
		solve();
	return 0;
}

Compilation message (stderr)

building.cpp: In function 'void read_file()':
building.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen(NAME ".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen(NAME ".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40