oj.uz

Submission #479258

# Submission time Handle Problem Language Result Execution time Memory
479258 2021-10-11T02:10:51 Z Mike4235 Building Bridges (CEOI17_building) C++17
100 / 100
 64 ms 9668 KB 
/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
// only when really needed

/* GNU G++17 7.3.0: No long long for faster code
   GNU G++17 9.2.0 (64 bit, msys 2): Long long only for faster code */
 
#include <bits/stdc++.h>
  
#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back
 
/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/
 
#define PI 3.1415926535897932384626433832795
#define INF 1000000000000000000
#define MOD 1000000007
#define MOD2 1000000009
#define EPS 1e-6

using namespace std;

int mode;
struct Line{
    mutable int a, b; mutable double k;
    bool operator<(const Line &p) const{
        return mode ? k < p.k : a < p.a;
    }
};
struct ConvexHull{
    multiset<Line> s;
    double div(int a, int b) {return 1.0 * a / b;}
    template<class T>bool isect(T x, T y) {
        if (y == s.end()) {x->k = INF; return 0;}
        if (x->a == y->a) {x->k = (x->b >= y->b ? INF : -INF);}
        else x->k = div(y->b - x->b, x->a - y->a);
        return x->k >= y->k;
    }
    void add(int a, int b) {
        auto z = s.insert({a, b, 0}), x = z++, y = x;
        while (isect(x, z)) z = s.erase(z);
        if (x != s.begin() && isect(--x, y)) isect(x, s.erase(y));
        while ((y = x) != s.begin() && isect(--x, y)) isect(x, s.erase(y));
    }
    int query(int x) {
        mode = 1;
        auto pos = s.lower_bound({0, 0, x});
        mode = 0;
        return -(pos->a) * x - pos->b;
    }
};
 
ConvexHull hull;
int n, h[100005], w[100005], dp[100005];

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

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    cin >> n;
    for1(i,1,n) cin >> h[i];
    for1(i,1,n) cin >> w[i];

    int cur = w[1];
    hull.add(2 * h[1], -(h[1] * h[1] - cur));
    for1(i,2,n) {
        dp[i] = hull.query(h[i]) + h[i] * h[i] + cur;
        cur += w[i];
        hull.add(2 * h[i], -(h[i] * h[i] - cur + dp[i]));
    }

    cout << dp[n];
    
}

Compilation message

building.cpp: In member function 'long long int ConvexHull::query(long long int)':
building.cpp:56:41: warning: narrowing conversion of 'x' from 'long long int' to 'double' [-Wnarrowing]
   56 |         auto pos = s.lower_bound({0, 0, x});
      |                                         ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3688 KB Output is correct
2 Correct 47 ms 3696 KB Output is correct
3 Correct 45 ms 3684 KB Output is correct
4 Correct 40 ms 3520 KB Output is correct
5 Correct 42 ms 4804 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 44 ms 3688 KB Output is correct
7 Correct 47 ms 3696 KB Output is correct
8 Correct 45 ms 3684 KB Output is correct
9 Correct 40 ms 3520 KB Output is correct
10 Correct 42 ms 4804 KB Output is correct
11 Correct 45 ms 3860 KB Output is correct
12 Correct 45 ms 3728 KB Output is correct
13 Correct 34 ms 3764 KB Output is correct
14 Correct 46 ms 3784 KB Output is correct
15 Correct 64 ms 9668 KB Output is correct
16 Correct 48 ms 4804 KB Output is correct
17 Correct 22 ms 3708 KB Output is correct
18 Correct 23 ms 3604 KB Output is correct