Submission #1024264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024264		trMatherz	Building Bridges (CEOI17_building)	C++17	100 / 100	60 ms	9812 KiB

building

#include <iostream> //cin, cout


// #include <fstream>
// std::ifstream cin ("tracking2.in");
// std::ofstream cout ("tracking2.out");





// includes
#include <cmath> 
#include <set>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>
#include <chrono>
#include <bitset>
#include <complex>




//usings 
using namespace std;
using namespace __gnu_pbds;


// misc
#define ll long long
#define ld long double
#define pb push_back
#define pq priority_queue
#define ub upper_bound
#define lb lower_bound
template<typename T, typename U> bool emin(T &a, const U &b){ return b < a ? a = b, true : false; }
template<typename T, typename U> bool emax(T &a, const U &b){ return b > a ? a = b, true : false; }
typedef uint64_t hash_t;

// vectors
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vpii vector<pair<int, int>>
#define vvpii vector<vector<pair<int, int>>>
#define vppipi vector<pair<int, pair<int, int>>>
#define vl vector<ll>
#define vvl vector<vl>
#define vvvl vector<vvl>
#define vpll vector<pair<ll, ll>>
#define vvpll vector<vpll>
#define vb vector<bool>
#define vvb vector<vb>
#define vs vector<string>
#define sz(x) (int)x.size()
#define rz resize
#define all(x) x.begin(), x.end()
#define vc vector<char>
#define vvc vector<vc>


// pairs
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define f first
#define s second

// sets
#define si set<int>
#define sl set<ll>
#define ss set<string>
#define in insert
template <class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// maps
#define mii map<int, int>
#define mll map<ll, ll>

// loops
#define FR(x, z, y) for (int x = z; x < y; x++)
#define FRE(x, z, y) FR(x, z, y + 1)
#define F(x, y) FR(x, 0, y)
#define FE(x, y) F(x, y + 1)
#define A(x, y) for(auto &x : y)



struct Line {
    mutable ll k, m, p;
    bool operator<(const Line &o) const { return k < o.k; }
    bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
    static const ll inf = (ll) 1e18 + 7; 
    ll div(ll a, ll b) {return a / b - ((a ^ b) < 0 && a % b);}
    bool isect(iterator x, iterator y){
        if(y == end()) return x->p = inf, 0; 
        if(x->k == y->k) x->p = ( x->m > y->m ? inf : -inf ); 
        else x->p = div(y->m - x->m, x->k - y->k);
        return x->p >= y->p; 
    }
    void add(ll k, ll m){
        auto z = in({k, m, 0}), y = z++, x = y; 
        while(isect(y, z)) z = erase(z); 
        if(x != begin() && isect(--x, y)) isect(x, erase(y));
        while((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y)); 
    }
    ll get(ll x){
        auto y = *lb(x); 
        return y.k * x + y.m; 
    }
};


int main(){
    int n; cin >> n; vl a(n), b(n); A(u, a) cin >> u; A(u, b) cin >> u;
    vl pre(n + 1, 0); F(i, n) pre[i + 1] = pre[i] + b[i]; 
    LineContainer v; v.add(2 * a[0], -1 * ( a[0] * a[0] - b[0] ));
    FR(i, 1, n - 1){ 
        v.add(2 * a[i], -1 * (2 * a[i] * a[i] - pre[i + 1] - v.get(a[i]) + pre[i]));
    }
    cout << -v.get(a[n - 1]) + a[n - 1] * a[n - 1] + pre[n - 1] << endl;
} 

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