oj.uz

Submission #1108794

# Submission time Handle Problem Language Result Execution time Memory
1108794 2024-11-05T06:23:21 Z koukirocks Building Bridges (CEOI17_building) C++17
100 / 100
 69 ms 12764 KB 
#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;

struct Node {
    int l,r;
    pll ln;
    Node *lft,*rt;
    Node(int l,int r):l(l),r(r),ln({0,oo}),lft(nullptr),rt(nullptr) {};
    void update(pll ln2) {
        if (l==r) {
            if (ln2.F*l+ln2.S>=ln.F*l+ln.S) swap(ln,ln2);
            return;
        }
        if (ln.F<ln2.F) swap(ln,ln2);
        int mid=l+r>>1;
        if (ln2.F*mid+ln2.S<=ln.F*mid+ln.S) {
            if (!lft) lft=new Node(l,mid);
            lft ->update(ln);
            ln = ln2;
        } else {
            if (!rt) rt = new Node(mid+1,r);
            rt->update(ln2);
        }
        // cout<<l<<" "<<r<<" "<<ln.F<<" "<<ln.S<<" l r ln\n";
    }
    ll query(ll x) {
        int mid=l+r>>1;
        ll ans=ln.F*x+ln.S;
        if (x<=mid and lft) ans=min(ans,lft->query(x));
        else if (x>mid and rt) ans=min(ans,rt->query(x));
        return ans;
    }
};

int main() {
    speed;
    int n;
    cin>>n;
    vector<ll> h(n+1);
    vector<ll> pre(n+1);
    for (int i=1;i<=n;i++) {
        cin>>h[i];
    }
    for (int i=1;i<=n;i++) {
        cin>>pre[i];
        pre[i]+=pre[i-1];
    }
    vector<ll> dp(n+1);
    Node *rt = new Node(0,1e6);
    rt->update({-2*h[1],h[1]*h[1]-pre[1]});
    for (int i=2;i<=n;i++) {
        dp[i]=rt->query(h[i])+h[i]*h[i]+pre[i-1];
        rt->update({-2*h[i],h[i]*h[i]-pre[i]+dp[i]});
        // cout<<dp[i]<<" dp\n";
        // cout<<-2*h[i]<<" "<<h[i]*h[i]-pre[i]+dp[i]<<" ln\n";
    }
    cout<<dp[n]<<"\n";
    return 0;
}


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

Compilation message

building.cpp: In member function 'void Node::update(pll)':
building.cpp:37:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         int mid=l+r>>1;
      |                 ~^~
building.cpp: In member function 'll Node::query(ll)':
building.cpp:49:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         int mid=l+r>>1;
      |                 ~^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 628 KB Output is correct
5 Correct 1 ms 592 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3616 KB Output is correct
2 Correct 45 ms 4636 KB Output is correct
3 Correct 44 ms 4432 KB Output is correct
4 Correct 37 ms 3920 KB Output is correct
5 Correct 33 ms 9032 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 2 ms 628 KB Output is correct
5 Correct 1 ms 592 KB Output is correct
6 Correct 45 ms 3616 KB Output is correct
7 Correct 45 ms 4636 KB Output is correct
8 Correct 44 ms 4432 KB Output is correct
9 Correct 37 ms 3920 KB Output is correct
10 Correct 33 ms 9032 KB Output is correct
11 Correct 58 ms 9768 KB Output is correct
12 Correct 64 ms 9800 KB Output is correct
13 Correct 54 ms 5288 KB Output is correct
14 Correct 69 ms 10312 KB Output is correct
15 Correct 34 ms 12764 KB Output is correct
16 Correct 32 ms 8996 KB Output is correct
17 Correct 25 ms 3664 KB Output is correct
18 Correct 24 ms 3664 KB Output is correct