oj.uz

Submission #1112566

# Submission time Handle Problem Language Result Execution time Memory
1112566 2024-11-14T10:45:43 Z InvMOD Building Bridges (CEOI17_building) C++14
100 / 100
 42 ms 19536 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define gcd __gcd
#define sz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define dbg(x) "[" #x " = " << (x) << "]"
///#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}

const int N = 2e5+5;
const ll MOD = 1e9+7;
const ll INF = 1e18;


struct LichaoOptMem{
    struct Line{
        ll a,b;
        Line(ll a = 0, ll b = 0): a(a), b(b) {}
        ll slope(){return a;}
        ll f(ll x){return (a == 0 && b == 0 ? LLONG_MAX : a*x + b);}
        ll intersect(Line x){return (x.b - b) / (a - x.a);}
    };

    vector<Line> st; int trsz;
    LichaoOptMem(int n = 0): st(n+1, Line()), trsz(n) {}

    void update(int l, int r, Line curLine){
        if(l > r) return;
        if(l == r){
            st[l] = (st[l].f(l) < curLine.f(l) ? st[l] : curLine);
            return;
        }
        else{
            int mid = l+r>>1;
            if(st[mid].f(mid) > curLine.f(mid)) swap(curLine, st[mid]);
            if(st[mid].slope() < curLine.slope()) update(l, mid-1, curLine);
            if(st[mid].slope() > curLine.slope()) update(mid+1, r, curLine);
        }
        return;
    }

    void addLine(ll a, ll b){
        return update(0, trsz, Line(a, b)), void();
    }

    ll query(int l, int r, ll x){
        if(l > r) return LLONG_MAX;
        if(l == r){
            return st[l].f(x);
        }
        else{
            int m = l+r>>1;
            if(x < m)
                return min(st[m].f(x), query(l, m-1, x));
            else if(x > m) return min(st[m].f(x), query(m+1, r, x));
            else return st[m].f(x);
        }
        return assert(1 == 0), 0;
    }

    ll query(ll x){
        ll val = query(0, trsz, x);
        return (val != LLONG_MAX ? val : 0);
    }
};

void solve()
{
    int n; cin >> n;

    vector<ll> h(n+1), w(n+1);
    FOR(i, 1, n) cin >> h[i];
    FOR(i, 1, n) cin >> w[i], w[i] += w[i-1];

    vector<ll> dp(n+1);
    /* Brute force
    FOR(i, 2, n){
        dp[i] = INF;
        FOR(j, 1, i-1){
            dp[i] = min(dp[i], dp[j] + (h[i] - h[j]) * (h[i] - h[j]) + (w[i-1] - w[j]));
        }
    }
    */

    LichaoOptMem lichao(*max_element(all(h)));
    FOR(i, 1, n){
        dp[i] = (i > 1 ? lichao.query(h[i]) + w[i-1] + h[i]*h[i] : 0);
        lichao.addLine(-2*h[i], h[i]*h[i] - w[i] + dp[i]);
    }

    cout << dp[n] <<"\n";
    return;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

Compilation message

building.cpp: In member function 'void LichaoOptMem::update(int, int, LichaoOptMem::Line)':
building.cpp:47:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |             int mid = l+r>>1;
      |                       ~^~
building.cpp: In member function 'll LichaoOptMem::query(int, int, ll)':
building.cpp:65:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |             int m = l+r>>1;
      |                     ~^~
building.cpp: In function 'int main()':
building.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
building.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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 348 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 468 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5456 KB Output is correct
2 Correct 33 ms 5456 KB Output is correct
3 Correct 33 ms 5456 KB Output is correct
4 Correct 30 ms 5200 KB Output is correct
5 Correct 30 ms 6736 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 348 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 33 ms 5456 KB Output is correct
7 Correct 33 ms 5456 KB Output is correct
8 Correct 33 ms 5456 KB Output is correct
9 Correct 30 ms 5200 KB Output is correct
10 Correct 30 ms 6736 KB Output is correct
11 Correct 42 ms 5372 KB Output is correct
12 Correct 41 ms 5200 KB Output is correct
13 Correct 29 ms 3920 KB Output is correct
14 Correct 41 ms 5712 KB Output is correct
15 Correct 27 ms 6736 KB Output is correct
16 Correct 27 ms 6920 KB Output is correct
17 Correct 22 ms 19536 KB Output is correct
18 Correct 17 ms 3664 KB Output is correct