Submission #1110264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110264		ducanh0811	Building Bridges (CEOI17_building)	C++14	100 / 100	36 ms	19536 KiB

building

/***
 *        ___       ___       ___       ___
 *       /\__\     /\  \     /\__\     /\__\
 *      /:| _|_   _\:\  \   /:/ _/_   /::L_L_
 *     /::|/\__\ /\/::\__\ /:/_/\__\ /:/L:\__\
 *     \/|::/  / \::/\/__/ \:\/:/  / \/_/:/  /
 *       |:/  /   \:\__\    \::/  /    /:/  /
 *       \/__/     \/__/     \/__/     \/__/
 */

#define task ""
#include <bits/stdc++.h>
/**                         **/
typedef long long ll;
typedef long double db;
using namespace std;
/**                         **/
#define int long long
#define endl    '\n'
#define fi      first
#define se      second
#define pb      push_back
#define eb      emplace_back
#define pll     pair<ll,ll>
#define ALL(x)  x.begin(),x.end()
#define len(s)      ((int)(s.size()))
#define mask(i)     (1LL<<(i))
#define bit(i,j)    ((1LL<<(j))&(i))
#define on(i,j)     ((1LL<<(j))|(i))
#define off(i,j)    ((~(1LL<<(j)))&(i))
#define FOR(i,a,b)  for(ll i = (a); i <= (b); ++i)
#define FORD(i,a,b) for(ll i = (a); i >= (b); --i)
/**                         **/

int N;
#define MAXN 100005
int h[MAXN];
int w[MAXN];
int pref[MAXN];
const int INF = 1e18;

struct line{
    int a, b;
    line() : a(0), b(0) {};
    line(const int &a, const int &b): a(a), b(b) {};
    int value(const int &x) {return a * x + b;};
    int slope() {return a;};
};

struct LCTopt{
    int n;
    vector<line> st;
    LCTopt(const int &_size) : n(_size), st(_size + 1, line(0, INF)) {};
    void update(int l, int r, line F){
        if (l > r) return;
        int mid = (l + r) >> 1;
        if (l == r) return st[mid] = (F.value(l) < st[mid].value(l) ? F : st[mid]), void();
        if (st[mid].value(mid) > F.value(mid)) swap(st[mid], F);
        if (F.value(l) < st[mid].value(l)) update(l, mid - 1, F);
        if (F.value(r) < st[mid].value(r)) update(mid + 1, r, F);
    }
    void update(line F){ return update(1, n, F); };
    int query(int l, int r, int p){
        int mid = (l + r) >> 1;
        int value = st[mid].value(p);
        if (p == mid) return value;
        if (p < mid) return min(query(l, mid - 1, p), value);
        return min(query(mid + 1, r, p), value);
    }
    int query(int p) {return query(1, n, p);};
};

/**
6
3 8 7 1 6 6
0 -1 9 1 2 0
**/

void solve(){
    cin >> N;
    int MAX = 0;
    FOR(i,1,N) cin >> h[i];
    FOR(i,1,N) MAX = max(MAX, h[i]);
    FOR(i,1,N) cin >> w[i];
    FOR(i,1,N) pref[i]=pref[i-1]+w[i];
    LCTopt tree(MAX);
    tree.update(line(-2*h[1], h[1]*h[1] - pref[1]));
    FOR(i,2,N){
        int dpi = tree.query(h[i]) + pref[i-1] + h[i]*h[i];
        if (i == N) return cout << dpi, void();
        tree.update(line(-2*h[i], h[i]*h[i] + dpi - pref[i]));
    }
}

/**                         **/
int32_t main(){
    if (fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    solve();
    return 0;
}

Compilation message (stderr)

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

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