Submission #868683

#	Time	Username	Problem	Language	Result	Execution time	Memory
868683		jack1eno_1_2401	Building Bridges (CEOI17_building)	C++14	100 / 100	50 ms	73592 KiB

building

#include<bits/stdc++.h>

////Ta thuat
//#pragma GCC optimize("O2")
//#pragma GCC target("avx,avx2,fma")

#define MOD 1000000007
#define fi first
#define se second
#define int long long
#define ii pair<int,int>
#define Dennis "Top1Server"
#define Jack1e "DB bainao"
#define heap_max(a) priority_queue<a>
#define heap_min(a) priority_queue<a, vector<a>, greater <a>>
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define el cout << '\n'
#define rep(i, n) for(int i = 0; i < (n); i++)
#define For(i, a, b) for(int i = (a); i <= (b); i++)
#define Fod(i, a, b) for(int i = (a); i >= (b); i--)
#define bit(x, i) ((x >> i) & 1)

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b){
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b){
    if (a < b) return a = b, true;
    return false;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r) {return l + rng() % (r - l + 1);}
const int N = 1e6;

struct line{
    int a, b;
    line(){
        a = 0;
        b = 1e18;
    }
    line(int aa, int bb){
        a = aa;
        b = bb;
    }
    int eval(int x){
        return a*x + b;
    }
};

int mx;
line sg[4*N];
void update(int id, int l, int r, line myLine){
    if(l == r){
        if(sg[id].eval(l) > myLine.eval(l)){
            sg[id] = myLine;
        }
        return;
    }
    int m = (l + r) / 2;

    if(sg[id].a > myLine.a) swap(sg[id], myLine);
    if(sg[id].eval(m) > myLine.eval(m)){
        swap(sg[id], myLine);
        update(id*2+1, m+1, r, myLine);
    }else{
        update(id*2, l, m, myLine);
    }
}

int get(int id, int l, int r, int x){
    if(l == r){
        return sg[id].eval(x);
    }
    int m = (l + r) / 2;
    if(x <= m){
        return min(sg[id].eval(x), get(id*2, l, m, x));
    }else{
        return min(sg[id].eval(x), get(id*2+1, m+1, r, x));
    }
}

int dp[N], sum[N];
int n, h[N], w[N];

void solve(){
    cin >> n;
    For(i,1,n) cin >> h[i];
    For(i,1,n){
        cin >> w[i];
        sum[i] = sum[i-1] + w[i];
    }

    update(1, 1, N,
        line(-2*h[1], dp[1] + h[1]*h[1] - sum[1]));
    For(i,2,n){
        int c = h[i]*h[i] + sum[i-1];
        int tmp = get(1, 1, N, h[i]);
        dp[i] = tmp + c;

        update(1, 1, N, 
            line(-2*h[i], dp[i] + h[i]*h[i] - sum[i]));
    }
    cout << dp[n];
}

main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define TASK "BRIDGEPOL"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    int T = 1;
    //cin >> T;
    while(T--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

building.cpp:109:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  109 | main(){
      | ^~~~
building.cpp: In function 'int main()':
building.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
building.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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